[es] - jedinstvena kombinatorika...?

dootzky
Programmer, PHP, Python, web development
beograd

Član broj: 85021
Poruke: 134
*.ewepc.net.

+1 Profil

^{12.04.2007. u 09:53 - pre 219 meseci}

cao ljudi !

vec sam pretrazio forum, i ima nekoliko slicnih stvari koje me zanimaju, ali imam jedinstven zadatak:

ako imam predefinisan set karaktera (cifre i mala slova, znaci "0123456789abcdefghijklmnopqrstuvwxyz"),
i trebam da napravim SVE-MOGUCE-KOMBINACIJE tih cifara, u tekstualnom fajlu, ali da je duzina "jednog sloga" N karaktera (znaci 4, 6, ili 8...)

- da li postoji neki dojajni algoritam koji radi tu kombinatoriku tj. permutacije za mene, ili cu morati sam da radim od nule?

svakako umem da uradim sve ostalo sto se tice okruzenja i sl, ali sam algoritam za rotaciju tih elemenata mi je dosta... jeziv!

znaci ideja je da dobijem txt file od tipa 14MB+, tu ce biti HILJADE i HILJADE kombinacija :P
npr:

0000
0001
0002
...
0099
0100
0101
...
a000
a001
a002
....
abc1
abc2
....
ab1c
ab2c
ab3c
ab4c
....
....

znaci to je mozda i NEBULOZNO puno kombinacija, ali kolege na poslu su me zamolile da im napravim takav fajl za neko hardversko testiranje, pa ako neko ima ideju kako da izgenerisem txt fajl sa 81237498712364987263 linija resenja -> pls do say

hvala sto ste citali,
poz,
d

Odgovor na temu

boysha

Član broj: 138554
Poruke: 6
*.yubc.net.

Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 11:51 - pre 219 meseci}

Koliko ja znam, .net nema dostavljenu klasu za kombinatoriku. To što ti tražiš, ako se dobro sećam, su varijacije bez ponavljanja. Ako budeš napravio algoritam, ajd okači source klase negde i javi ;)
Možda ovako nešto, gde je svaki član rezultujuće liste object[k]:

Code:

public static class Kombinatorika
{
  public static long BrojVarijacija(int duzinaNiza, int k);
  public static ArrayList Varijacije(object[] niz, int k);
  public static ArrayList Varijacije(object[] niz, int k, int pocetak, int kraj);

  // ...
}

Odgovor na temu

dootzky
Programmer, PHP, Python, web development
beograd

Član broj: 85021
Poruke: 134
*.ewepc.net.

+1 Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 12:46 - pre 219 meseci}

yo!

heh, ma znas sta je fora, kopam po glavi, trazim ideje... to bi moralo da se radi nekako rekurzivno, svakako..

inace, rekli su mi momci sta ocekuju: taj set slova: brojevi 0-9, i sva mala slova abecede - ako pravimo stepen N od 5 karaktera, znaci da blok svih kombinacija bude 5 karaktera, ocekuje se fajl od 21 GB!!!!!!!

lagali su me kad su rekli da je to 14mb!! to je, kao, bila fora. ^_^ ono: "ha-ha". :P

dakle, to mora da je jako "interesantno" napraviti, ali kapiram globalno:

1) imam niz karaktera koje hocu da kombinujem "123456abc". recimo. stepen N je 3.

moram petljom da idem kroz:
- svaki clan, sa rotacijom svih ostalih clanova, sa minimalnom duzinom N.
e sad, nije frka trcati kroz clanove niza, opusteno, ali rotirati ostale, u smislenom redosledu, po vaznosti - to je malo jebeno..

i sada gledam, kako bi na kraju i testirao da li to valja? :| mislim, najbezbolnije je uzeti "mali" primer, i onda rucno tj. peske proveriti rezultate.. npr:

123
124
125
126
12a
12b
12c

132
134
135
136
13a
13b
13c

142
143
145
146
14a
14b
14c

152
153
154
156
15a
15b
15c

i ok, vidis da postoji po 7 rotacija za svaku kombinaciju, znaci to bi "generalno" trebalo da je izvodljivo, vec vidim nekakav algoritam za ovo, nije obavezno nemoguce, jer - sve sto se ponavlja, moze da se sablonizuje, a sve sto se sablonizuje - moze da se iskodira!

problem je sto je duzina sloga N promenljiva, i lako je ovo uraditi sa N = 3.
ajde da probamo za N=4

1234
1235
1236
123a
123b
123c

1243
1245
1246
124a
124b
124c

1253
1254
1256
125a
125b
125c

hm hm...
vidis, sada ima 6 elemenata u svakom "bloku" slogova... hmmmmm ..

thinking, thinking......

ajde brisem da zavrsim nesto drugo, pa cu probati da napravim neku doslednost ovde, i onda da se to i iskodira.... izem ti i zahtev, u cetvrtak poslepodne!

a bio je tako lep dan! hahahha :P

poz,
dootzky

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 12:47 - pre 219 meseci}

Evo ti jednostavno resenje, neoptimozovano doduse, bazirano na IEnumerator. Cisto da vidis kako moze:

Code:

        static void Main(string[] args)
        {
            foreach (string p in Permutations(4, "0123456789abcdefghijklmnopqrstuvwxyz"))  Console.WriteLine(p);
        }

        public static IEnumerable<string> Permutations(int length, string chars)
        {
            foreach(char c in chars)
                if (length==1) yield return c.ToString();
                else foreach (string s in Permutations(length - 1, chars)) yield return c + s;
        }
    }

Sad citam tvoj drugi post, jel ti trazis permutacije sa ponavljanjem ili bez? Prvo si trazio sa ponavljanjem, sad bez...

_{[Ovu poruku je menjao mmix dana 12.04.2007. u 13:58 GMT+1]}

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Odgovor na temu

dootzky
Programmer, PHP, Python, web development
beograd

Član broj: 85021
Poruke: 134
*.ewepc.net.

+1 Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 13:04 - pre 219 meseci}

v-a-u.

sto bi rekao jedan lik na nekom stranom forumu: "man, if i didn't have a girlfriend right now - i'd kiss you!!", a odgovor je bio: "it's ok man, i love you too..."

))))))

wow!
respect!!

doduse, nisam siguran da li brojevi smeju ili ne smeju da se ponavljaju u ovom smislu, ali resenje sa 2 foreach petlje... CCCCC
jezivo!!

thanks man,
idem da im dam to dole, pa nek' se sad oni snadju

poz,
i hvala jos jednom! prosto genijalno!!

Odgovor na temu

dootzky
Programmer, PHP, Python, web development
beograd

Član broj: 85021
Poruke: 134
*.ewepc.net.

+1 Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 13:06 - pre 219 meseci}

a za permutacije - nisam siguran za ponavljanje, sekund da pozovem da pitam - editujem post za sekund!

- ok - pitao sam - treba i ponavljanje, znaci - ovaj tvoj algoritmic je bio PUN POGODAK!!!

sada njima treba da se odradi dinamicki broj N slogova, sa cu to ja da spakujem za par minuta, ali ovo ostalo je prosto GENIJALNO!

hvala neverovatno puno,
ustedeo si mi verovatno 6 dana truda, zivaca i noci nespavanja ^_^

poz,
dootzky

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 13:16 - pre 219 meseci}

Imaj samo u vidu da je ovo sto sam ti okacio vise edukativni kod nego nesto primenljivo u praksi. Bazira se na iteratorima i na spajanju stringova, sto je sve veoma sporo, sa N=1..5 ces se nekako i provuci, sve preko ce trajati sto godina

Odgovor na temu

dootzky
Programmer, PHP, Python, web development
beograd

Član broj: 85021
Poruke: 134
*.ewepc.net.

+1 Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 13:34 - pre 219 meseci}

haha.. pa video sam, pustio sam, krenuo sam da pisem fajl... nije stigao ni do:
03xxx

i fajl je vec 25MB, a trajalo je 10 min ^_^

hehe.. neka, ok, stagod, neka to zavrsi posao, pa makar radilo i 3 veceri za redom ^_^

hvala man! :)

poz,
d

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: jedinstvena kombinatorika...?

^{12.04.2007. u 14:34 - pre 219 meseci}

Evo ti i brzi iterator, koji nije baziran na rekurziji i radi sa char[] umesto sa spajanjem stringova

Code:

        public static IEnumerable<char[]> Permutations(int length, string chars)
        {
            char[] res = (char[])Array.CreateInstance(typeof(char), length);
            int[] indexes = (int[])Array.CreateInstance(typeof(int), length);
            int pointer = length - 1;
            int charlen = chars.Length;
            // setup
            for (int i = 0; i < length; i++) res[i] = chars[0];
            for (int i = 0; i < length; i++) indexes[i] = 0;

            while (indexes[0] < charlen)
            {
                // pust rezultat u enumerator
                yield return res;

                // sredi indexe
                indexes[pointer]++;
                if (indexes[pointer] < charlen) res[pointer] = chars[indexes[pointer]];
                for (int i = length-1; i > 0; i--)
                {
                    if (indexes[i] >= charlen)
                    {
                        indexes[i] = 0;
                        res[i] = chars[0];
                        indexes[i - 1]++;
                        if (indexes[i-1] < charlen) res[i-1] = chars[indexes[i-1]];
                    }
                }
            }
        }

Odgovor na temu