» »

[C++] Generiranje vseh možnih kombinacij

francy ::

Živijo!

Rabil bi pomoč pri generiranju vseh možnih kombinacij iz 82 različnih znakov (brez ponavlanja) dolžine med 8 in 63.

Kako bi bilo to najlažje izvesti?
  • spremenilo: francy ()

mr1two ::

Samo ideja:
Narediš 2 tabeli, eno prazno, dolžine, ki jo boš napolnil. In eno polno, z znaki, ki so na voljo.
Malo pozankaš, prazneš eno tabelo(filaš vanjo null vrednosti) in filaš drugo(z vrednostjo, ki je bila na nekem mestu v prejšnji tabeli), vmes pa preverjaš, da nebi dal slučajno "praznega" znaka v novo tabelo. Uporabljaš random naslavljanje tabele.
Ni ravno učinkovita zadeva(zna trajat mal več časa za daljše tabele zaradi falš zadetkov), ampak je prva, ki se je spomnem in ni preveč komplicirana.

mr1two ::

Evo, ker sem ravno na času, moja na hitro spackana koda zgleda nekako tako. Sicer je java, ampak lahko pa vidiš princip.
package testni;

import java.util.Scanner;

public class Glavni {

	
	public static void main(String[] args) {
		// najprej nastavimo neko tabelo, ki jo napolnemo z nekimi izbranimi znaki
		char[] tabela=new char[80];
                //ker je najbolj simpl kar mal porabit ascii nabor znakov, porabim kar to
		for(int i=0;i<tabela.length;i++)
		{
			tabela[i]=(char)(i+48);
		}
		Scanner sc= new Scanner(System.in);
		System.out.print("Vnesi dolžino: ");
		int dolz=sc.nextInt();
                //deklaracija nove tabele, v Cju ni tko simpl, ampak lahko rešiš drugače(daš kar isto veliki tabeli, pa greš potem samo do izbrane meje, ki je v tem primeru dolz
		char[] izbrani=new char[dolz];
		boolean narejeno=false;
		int a=0;
		int j=0;
		do
		{       //tuki pa malo na random izbiraš znake. Če ni izbran, potem ga zapišeš v novo tabelo, sicer pa ne
			a=(int)(Math.random()*tabela.length);
			if(tabela[a]!='*')
			{
				izbrani[j]=tabela[a];
				tabela[a]='*';
				j++;
				if(izbrani.length==j){
					narejeno=true;
					break;
				}
			}
		}while(!narejeno);
		//samo še izpis
		System.out.println("Cestitamo, izbrana kombinacija je:");
		for(j=0;j<izbrani.length;j++)
		{
			System.out.print(izbrani[j]+" ");
		}
		
	}

}


Izbor znakov z zgornjo kodo je krneki, ampak princip pa še kr dela :)

SiByte ::

Google: c++ permutations combinations
Intel i7 4770k @ 5,0GHz | ASUS Maximus VI Extreme | ASUS GTX 760 2GB @ SLI
2x8GB Corsair DDR3 @ 2400MHz | 240GB SSD Intel 530 @ Raid0 | 2TB WD Black

Zgodovina sprememb…

  • spremenil: SiByte ()

mallard ::

Število kombinacij 63 elementov od 82-ih: 63 C 82 = n!/(k!(n-k)!) = 82! / (82! * 19!) = 1971038235969316800, okroglo 10x manj kot je možnih vrednosti v 64-bitnem celem številu. Prištej še 62C82, 61C82, 60C82 itd... Glede na to, da bi samo sprehod čez vsa možna 64-bitna števila trajal okrog 100, 200 let na PC-ju... upam, da ne misliš zapisovat rezultatov na disk :)

mr1two ::

Eh, slabo sem prebral, kaj si želel imeti(se posipljem s pepelom)

francy ::

Hvala vsem! mi je že uspelo.

@mallard: to je bilo vse bolj teoretično :) rabil sem del izmed vseh kombinacij vpisat moraš začetek potem pa ti naslednjih 1000 on izpiše :D

Spura ::

Popravil napako:
    private static Iterable<String> getCombs(final int atLeast,
            final int atMost, final char[] charPool) {
        return new Iterable<String>() {

            @Override
            public Iterator<String> iterator() {
                if (charPool.length == 0 || atLeast > atMost || atMost <= 0 || atLeast <= 0) {
                    return new Iterator<String>() {

                        @Override
                        public boolean hasNext() {
                            return false;
                        }

                        @Override
                        public String next() {
                            throw new NoSuchElementException();
                        }

                        @Override
                        public void remove() {
                            throw new UnsupportedOperationException();
                        }

                    };
                } else {
                    return new Iterator<String>() {
                        // string variables
                        private char[] strChars;
                        private int[] strCharIdx;
                        private int strLength;
                        // iteration variables
                        private boolean hasNext = false;
                        private boolean alreadyCheckedNext = false;
                        private String nextReturn = null;

                        // returns false if can't roll over a char
                        private boolean rollOverChar(int idx) {
                            if (idx < 0) {
                                return false;
                            } else if (strCharIdx[idx] == charPool.length - 1) {
                                if (idx >= atLeast) strLength--;
                                return rollOverChar(idx-1);
                            } else {
                                strChars[idx] = charPool[++strCharIdx[idx]];
                                for(int i = idx + 1;i < strLength;i++) {
                                    strChars[i] = charPool[0];
                                    strCharIdx[i] = 0;
                                }
                                return true;
                            }
                        }

                        @Override
                        public boolean hasNext() {
                            if (!alreadyCheckedNext) {
                                alreadyCheckedNext = true;
                                if (strChars == null) { // prva iteracija
                                    strChars = new char[atMost];
                                    strCharIdx = new int[atMost];
                                    for (int i = 0; i < atLeast; i++) {
                                        strChars[i] = charPool[0];
                                        strCharIdx[i] = 0;
                                    }
                                    nextReturn = new String(strChars, 0,
                                            atLeast);
                                    strLength = atLeast;
                                    hasNext = true;
                                } else {
                                    if (strLength < atMost) {
                                        // expand
                                        hasNext = true;
                                        strChars[strLength] = charPool[0];
                                        strCharIdx[strLength] = 0;
                                        strLength++;
                                    } else {
                                        hasNext = rollOverChar(strLength-1);
                                    }
                                }
                                if (hasNext)
                                    nextReturn = new String(strChars, 0,
                                            strLength);
                            }
                            return hasNext;
                        }

                        @Override
                        public String next() {
                            if (hasNext()) {
                                alreadyCheckedNext = false;
                                return nextReturn;
                            } else {
                               throw new NoSuchElementException();
                            }
                        }

                        @Override
                        public void remove() {
                            throw new UnsupportedOperationException();
                        }
                    };
                }
            }
        };
    }


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Naloga (Java)

Oddelek: Programiranje
15529 (263) Ciklamen
»

Rabim pomoč z nekaj nalogami v c++

Oddelek: Programiranje
5283 (260) kopernik
»

[JAVA] algoritem za iskanje....{nujno!}

Oddelek: Programiranje
5495 (369) gtramt1
»

[C++] Podatkovne Strukure - Kombinacije

Oddelek: Programiranje
6568 (568) BigWhale
»

Problem (za Stratosa?)

Oddelek: Programiranje
371075 (425) Thomas

Več podobnih tem