Multinomial Kombinatorik i C#

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace Search
{
    /*
    Generate subscript permutations in lexigraphical order.  The first permutation
    on the subscripts is 0 1 2 3 4 5 6.  The next "smallest" permutation preserves as
    much of the previous one (starting at index 0), and increments the first subscript j (counting from the end) such that j < j+1.  We would get:
    0 1 2 3 4 6 5.  Continuing, we note that the last j for which j < j+1 is the
    4 6 pair, so we switch the 4 and 5 (5 is the smallest element that is bigger than the j (4) element, getting 0 1 2 3 5 6 4.  We sort the tail starting at the j+1 element to get 0 1 2 3 5 4 6, which is the next permutation in lexagraphical order after the previous one, 0 1 2 3 4 6 5.
    */
    public class Permute <T>
    {
        public List<T> collect;
        public int[] sub;
        public double maxReturns=1;
        public double totReturns = 0;
        bool firstTime = true;
        public Permute(List<T> col)
        {
            collect = col;
            for (double k = 1; k <= col.Count; k++)
                maxReturns *= k;
           
            sub = new int[collect.Count];
        }

        void checkTot()
        {
                    //because we can "cut", total returns need not equal maxReturns
            if (totReturns > maxReturns)
                throw new ApplicationException("wrong number permutations calculated");
        }

        public void cut(int position)
        {
            //Cut off all selections beneath position, so that the next call
            //to next will return the next selection at position, and the first
            //selection for the children thereunder.  Position is zero based

            if (position >= sub.Length - 1)
                return;
            //sort tail to get in order
            System.Array.Sort(sub, position + 1, sub.Length - position - 1);
            //reverse the tail so that the next permutation must increment position.
            reverse(position + 1);
        }

        List<T> formCollection()
        {
            List<T> result = new List<T>(sub.Length);
            for (int i = 0; i < sub.Length; i++)
                result.Add(collect[sub[i]]);

            return result;

        }

        public List<T> next()
        {
                /*
                we want to return permutations in lexical order (in the subscripts).
                thus:
                1 2 3 4
                1 2 4 3
                    ....
                4 3 2 1
                */

                //get the next permutation.  Return null when we are out.
           
            if (firstTime)
            {
                firstTime = false;
                totReturns++;
                return formCollection();
            }

            int incr = -1;
                //find the first element (starting at the right) that can be incremented
            for (int j = sub.Length - 2; j >= 0; j--)
            {
                if (sub[j] < sub[j+1])
                {
                    incr = j;
                    break;
                }
            }
                /*note that sub [incr] < sub[incr+1] > sub[incr+2] > ... > sub[n]
                  we have already visited all permutations that start with
                    sub[0], sub[1], ..., sub[incr]
                  so the next permutation in lexical order will have sub[incr] incremented
                  by 1.
            */

            if (incr < 0)
            {
                checkTot();
                return null;
            }

                    //find the first element larger than the one we can increment
            int switcher = -1;
            for (int i = sub.Length - 1; i >= 0; i--)
            {
                if (sub[i] > sub[incr])
                {
                    switcher = i;
                    break;
                }
            }

            if (switcher < 0)
            {
                checkTot();
                return null;
            }

                    //switch the element we are incrementing, and the one we are incr. to
            int hold = sub[switcher];
            sub[switcher] = sub[incr];
            sub[incr] = hold;

            //sort tail of array from incr+1 to end
            reverse(incr + 1);

            totReturns++;
            return formCollection();

        }

        public IEnumerable<List<T>> permutations()
        {

            /*enumerator to return all permutations.  Use thus:
            foreach (List<int> ans in permute.permutations())
            {
                    //do something with ans 
            }
            where permute is a Permutation
            */
            restart();

            List<T> ans;
            while ((ans = next()) != null)
            {
                yield return ans;
            }
        }

        public void restart()
        {
            totReturns = 0;
            for (int i = 0; i < collect.Count; i++)
                sub[i] = i;
            firstTime = true;
            totReturns = 0;
        }

        void reverse(int start)
        {
            //this just puts the tail in order.  We need not do a full sort since we
            //know the elements are in reverse order.
            int k = start;
            int m = sub.Length - 1;
            int hold;

            while (k < m)
            {
                hold = sub[k];
                sub[k] = sub[m];
                sub[m] = hold;
                k++;
                m--;
            }
        }
    }
}

/////////////////////////
// Use of Permute class /
/////////////////////////
List<int> problem = new List<int>(numItems);
problem.Add(0);
problem.Add(1);
problem.Add(3);
problem.Add(2);
problem.Add(3);
problem.Add(1);

Permute<int> permute = new Permute<int>(problem);

foreach (List<int> ans in permute.permutations())
{
    foreach (int val in ans)
        writer.Write(val + ", ");
    writer.WriteLine();

}

Jeg skal lige hører inden jeg går for meget i gang...

Hvor meget forstand har du på O(n) og algoritmer? Bruteforce, Recursive algoritmer, Devide and Conquer og Dynamic Programming??

Hvor store bliver dine talrækker evt?, for  som det ser ud PT... når du op på 20 vil du ikke se computeren give dig løsningen i din livstid...

PT ser det ud til at du har en O(n!) algoritme, og det må siges ikke at være godt...

I dit tilfælde kan du nok bruge Dynamic Programming til at lave dig nogle shortcuts i den situation hvor der er tal der går igen og du er interesseret i de unikke permutationer...

Jeg kan dog ikke lige overskue det nu, da jeg skal i byen osv... desuden vil jeg lige hører om de overstående problemer er noget du har tænkt over...

Og kender du til træer?...

Her er en lille hurtig skitse på hvordan en algorimte kan finde frem til løsnigner... talene er Indices i dit array...

Figur 2 går ud på af hvis fx index 0 og 1 (makeret som 1 og 2)... er ens, så behøver du kun finde løsninger til en af dem da den anden vil give de samme løsninger...

her er link: http://dotjem.com/Permutation.pdf

Men må afsted nu... forklarer mere dybdegående senere...

Hehe. Det er naturligvis et meget relevant spørgsmål og jeg er fuldt ud klar over at mit problem løber løbsk med størrelsen, men der er et par forhold, der spiller ind som giver mig forhåbning om, at kunne løse mindre, men stadig relevante, problemer.

Min forhåbning er at kunne permutere lister i størrelsesordenen 15-20 og permutteringsprocessen skal ses som et led i en masterplan om at kunne løse et NP hårdt optimeringsproblem til (nær)-optimalitet.

Jeg skal finde den bedste placering af n elementer i en liste og jeg er i stand til at evaluere, hvor god placeringen har været med en objektfunktion.

Det dårlige ved mit problem er, at del evaluering af placeringen ikke er mulig. Dermed falder Branch and bound, dynamic programming og andre søgeteknikker til jorden(right??)

Det "gode" ved problemet er, at elementerne i listen kun kan antage 6 værdier og at de ofte kun vil antage et antal mindre end 6. Dermed har jeg en forhåbning om, at jeg vil ligge et stykke under worst case running time O(n!).

Jeg er meget interessert i andre måder at finde den optimale placering på, når man ikke kan delevaluere, men jeg er bange for at det er en forudsætning for de fleste søge teknikker.

Så jeg satser på en algoritme, der kan give mig alle unikke permutationer indtil computeren sprænger i luften(ved ikke hvornår det vil ske, men omkring 20 var også min forhåbning) og så evaluerer jeg dem alle sammen for at finde den bedste. Sådan populært sagt.

Allan

Hmm...  så først din skitse efter ovenstående...

Skal lige tænke over din træ struktur med indeks på nodes. Måske det slet ikke er så tosset en idé.

Probemet med at bruge Permute klassen ovenstående er, at jeg ikke kan lure, hvordan man kan smide symmetri permutationer væk inden de genereres.

Vender tilbage senerer
Allan

Lige inden jeg går i seng.. måske præget af en øl eller 2, 3, 4..... 10 stykker :P

Men den måde du smider de "allerede beregnede" permutationer væk på er at gemme en liste over dem... dette er der en række muligheder i for at gøre den hurtigere at finde dem...

"jagged arrays" eller lister der indeholder lister er ikke nogen dårlig ide evt..

Det du skal se på ud fra listen er at når du går et step ned i træet, så er der 2 faktorer der spiller ind...

A. Hvor lang de givende array er (resten af det)...
B. Hvilket tal udvælger vi nu...

Hvis du fx har en liste som du selv giver: [0,1,3,2,3,1] (og lad os lige ingnorerer 0 reglen til at starte med)...

Så har du som den første et 0 Hvor du så skal beregner permutationer for [1,3,2,3,1] så et 1 hvor det er for [0,3,2,3,1] osv... sat overskueligt op:

0: [1,3,2,3,1]
1: [0,3,2,3,1]
3: [0,1,2,3,1]
2: [0,1,3,3,1]
3: [0,1,3,2,1]
1: [0,1,3,2,3]

Der kan du undlade de sidste to beregninger ud fra at du har lagret at du har fundet løsnignen på 3 og længden 5 med [x1,x2,x3,x4,x5] som tal, for det givne array... samt 1 og længden 5..... så rykker vi et tan ned:

0: [1,3,2,3,1] v
- 1: [3,2,3,1] v
  - 3: [2,3,1] v
  - 2: [3,3,1] v
  - 3: [3,2,1] x
  - 1: [3,2,3] v
- 3: [1,2,3,1] v
  ...
- 2: [1,3,3,1] v
  ...
- 3: [1,3,2,1] x
- 1: [1,3,2,3] x
1: [0,3,2,3,1] v
- 0: [3,2,3,1] v
  ...
- 3: [0,2,3,1] v
  ...
- 2: [0,3,3,1] v
  ...
- 3: [0,3,2,1] x
- 1: [0,3,2,3] v
  ...
3: [0,1,2,3,1] v
- 0: [1,2,3,1] v
  ...
- 1: [0,2,3,1] v
  ...
- 2: [0,1,3,1] v
  ...
- 3: [0,1,2,1] v
  ...
- 1: [0,1,2,3] x
2: [0,1,3,3,1] v
- 0: [1,3,3,1] v
  ...
- 1: [0,3,3,1] v
  ...
- 3: [0,1,3,1] v
  ...
- 3: [0,1,3,1] x
- 1: [0,1,3,3] x
3: [0,1,3,2,1] x
1: [0,1,3,2,3] x

Når der findes løsniger for fx ( 0: [1,3,2,3,1] )... så gemmes dette i en tabel eller leste... eller jaged liste som tidligere nævnt... forklarer jeg om i morgen... men ideen er at når fx først ( 3: [0,1,2,3,1] ) er løst, så er ( 3: [0,1,3,2,1] ) også løst da det er det samme start tal, samt de samme tal indeholdt i arrayet...

en af udfordringerne er nok den måde du har valgt den skal fungere på med next, og at den teknisk set først skal beregne et resultat ved det kald, da det jo ville være en hel del næmmere med en recursiv algoritme...

Mit største problem er nok, at jeg ikke selv har lavet Permute klassen. Jeg kan godt lure hvad den gør i de forskellige løkker, men jeg forstår ikke helt hvorfor det virker..... Især Cut() er en abstrakt metode for mig.

Så derfor er en træ struktur attraktiv, da man bedre kan se princippet for sig. Synes jeg..

Dit ovenstående eksempel minder meget om en idé jeg selv har arbejdet med. Mit "problem" med metoden var at jeg
1) ikke kunne hitte ud af at lave et træ, der kunne repræsentere problemet.
2) Ikke kunne overbevise mig selv om, hvordan man kunne sikre at alle unødige undertræer forsvandt.

Jeg er nok også lidt hærget af at Maple bare lige kan vise antallet af unikke permutationer og op til en hvis størrelse også har list til at vise dem for mig.

Hvad vil du foreslå?

Det kan være meget svært at foreslå noget... for der er mange problemer man skal tage højde for...

Det nemmeste at lave ville nok være et recursivt kal der for hver værdi i et array klipper den værdi ud, og så kalder sig selv med det nye array... den løsning der kommer retur før så lige heftet den udklippede int foran...

Sådan kan du relativt næmt finde alle permutationer til et problem... så skal der så implementeres det med frasortering, det gør man ved at gemme en liste over hvad man har løst, har man løst et problem... så hopper man bare videre til det næste...

Ulæmpen her er helt klart hukommelsesforbrug... det kan explodere til uanedde mængder... derfor ville det være fordelagtigt hvis man kunne implementere det således at man ikke lavede "tmp" arrays til klippede arrays osv. men istedet kunne kører på det orginale array, og bare fortælle hvad den skulle gå uden om... hvis muligt...

I sidste ende bliver det en opvejning mellem hukommelse og ydelse... for når man gemme r løsninger, tager det naturligvis plads, mens hvis man ikke gør kan man ikke se om løsninger er fundet... det tager derfor tid...

Her er noget kode til en rekursiv løsning på problemet hvertfald... det kan du jo kigge på... PT har det alle de ulæmper ang. pladsforbrug jeg nævnte før... men det er mere hekset at rode med, men det er en start...

Modsat det kode du har nu, så returnere metoden PermuteUnique en fuld liste med alle unikke permutationer, frem for at få dem en efter en...

        public List<int[]> PermuteUnique(int[] arr)
        {
            List<int[]> value = new List<int[]>();
            List<int> known = new List<int>();
            if (arr.Length == 1)
            {
                value.Add(arr);
            }
            else
            {
                for (int i = 0; i < arr.Length; i++)
                {
                    if (!known.Contains(arr[i]))
                    {
                        known.Add(arr[i]);
                        List<int[]> solv = PermuteUnique(cut(arr, i));
                        foreach (int[] tarr in solv)
                        {
                            value.Add(remake(tarr, arr[i]));
                        }
                    }
                }
            }
            return value;
        }

        private int[] cut(int[] arr, int index)
        {
            int[] tmp = new int[arr.Length - 1];
            int j = 0;
            for (int i = 0; i < arr.Length; i++)
                if (i != index)
                    tmp[j++] = arr[i];
            return tmp;
        }

        private int[] remake(int[] arr, int preseed)
        {
            int[] tmp = new int[arr.Length + 1];
            tmp[0] = preseed;
            for (int i = 1; i < tmp.Length; i++)
                tmp[i] = arr[i - 1];
            return tmp;
        }

Med den kode tager denne permutation ca. 1 min at løse på min bærbar....

[1,2,3,4,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

altså 20 cifre, et max af 6 værdier... mindst "spredning"

Prøvede med en anden også... gav dog op efter 40 min og 2GB ram...

[0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1]

altså 20 cifre, et max af 6 værdier... mest "spredning"

Som en side bemærkning, så kan jeg jo lige benævne at når det er for at finde den "bedste" placering, laver man typisk vis ikke alle permutationer, men går sitedet efter at lave en ordenlig bunke random permutationer og så vælger man bare den bedste ud fra dem...

Det giver naturligvis ikke nødvendigvis den aller bedste af dem, men det giver kompleksiteter der er til at have med at gøre, og der er gode sandsynligheder for at man finder en der er tæt på den bedste...

"Som en side bemærkning, så kan jeg jo lige benævne at når det er for at finde den "bedste" placering, laver man typisk vis ikke alle permutationer, men går sitedet efter at lave en ordenlig bunke random permutationer og så vælger man bare den bedste ud fra dem..."

Mit hovedformål er faktisk at ende op med en metaheuristik. For at have en idé om hvordan denne præsterer, er det jo bare bekvemt at have nogle (nær)optimale løsninger at sammenligne sig med. Derfor har jeg rodet mig ud i indholdet af det orignale spørgsmål.

Derudover... Jeg har tidligere nævnt, at jeg havde eksperimenteret med en form for Tabulister/cut lister til at skære undertræer væk. Lidt i samme dur som dit forslag med (placering, værdi). Min bekymring omkring disse har været hukommelsesforbruget og derudover kunne jeg heller ikke få det til at dutte 100 %. Du nævner et forbrug på 2 GB og det er lige i overkanten til at være brugbart.

Hvordan måler man egentlig hukommelsesforbruget af sit program? Kigger i Task manager eller er der noget smartere.

Men det er netop derfor at Permutation klassen er attraktiv, da man kun lagrer en kombination af gangen og beregner sig frem til den næste.

Efter at have set din træstruktur tegning med indeks på nodes har jeg faktisk fundet på en meget nice idé med Permute klassen. Det var aldrig rigtig gået op for mig at man kunne have indeks på noderne i stedet for værdier, men du fik åbnet mine øjne for den opbygning.

Det gik pludselig op for mig, at alle permutationerne returneret fra permute klassen også kunne ses som udforsken af et træ. Blot har man pga. den leksikografiske udforsken mulighed for at cutte ret smart.

Med antagelsen om, at mine integers er sorteret i ascending order kan jeg nu benytte cut funktionen i Permute klassen på en ret smart måde. Såfremt man i next metoden finder ud af at to indeks, der indeholder samme værdi skal byttes(switcher og incrementer), så kan man sætte en global mustdie bool-værdi til true og cutte undertræet fra incrementer indekset. Dette virker fordi man kan være sikker på, at alle undertræer med den pågældende værdi på incrementers plads er udforsket. Det er leksikografien, der spiller ind. Så med den metode har man ikke brug for at huske hvad der har været prøvet.

Jeg takker mange 1000000 gange for dine input, som fik ledt mig i den rigtige retning.

Læg et svar. Du har mere en fortjent de 60 point

Allan

Skulle forresten nok have hørt bedre efter i graf teori og algoritmer og datastruktur - fagene.

Set i bakspejlet burde jeg nok kunne have luret træ tingen selv, men så er det jo superfedt, at man kan få hjælp herinde af nogen, der havde ørene åbne den dag det blev gennemgået og som havde forstået principperne ordentligt.

Det er vidst godt, at der skulle være mangel på arbejdskraft indenfor IT, så har man måske en chance selvom man har sovet for meget i studie tiden :-)

Endnu en gang tak

Allan

Prøvede lige dine to eksempler i Maple:

> numbperm([0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1],20);

                            3259095840000

> numbperm([1,2,3,4,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],20);

                              1860480

Kan måske forklare, hvorfor din bærbare brugte så meget ram på at gemme permutationerne i det første tilfælde og sammenholdt med det så vil Contains metoden vel brænde de 40 min af.

Antallet af permutationer i et multinomielt problem er (n! / k1!*k2!*..kt!), hvor n er antallet af elementer i listen og k1, k2, kt er antallet af unikke værdier.

Med mange forskellige værdier i listen vil antallet af permutationer nærme sig n!, mens de vil blive væsentligt reduceret, når der er mange indeks med samme værdi. I hvert fald for små værdier af n.

Allan

jeg ved godt hvorfor problemet opstod... det var bare lige for at gøre opmærksom på hvor gald det egentlig stod til... gennerelt set kunne man måske godt have en forhåbning om at komme igennem det selv om 3.259.095.840.000 er et stort tal... men man skal finde en måde at undgå det store hukommelsesproblem.... Hukommelses problemet er altid et problem med recursive algoritmer i starten... men man starter et sted... og så optimere man...

Det må jo så være det samme sted du står med din kode nu... ;)

Det er aldrig en dårlig ide at side med en blok ved siden af dig når du løser den her slags problemer, for man kan tegne sig ud af rigtig mange ting....

og et svar her fra...

Nu sad jeg lige og kiggede det kode der igennem... der er en del mere alm. ting som enten ikke giver mening eller som jeg ikke bryder mig om...

Først bryder jeg mig ikke om public fields... eller fields/metoder der ikke har en accessmodifyer på... dvs. de metoder der ikke har private, protected, public eller internal...

Nogle af de fields der er...

        public int[] sub;

Public?.. er det ikke lidt uhensigtsmæssigt at man kan rode med indices arrayet externt?

        public double maxReturns=1;
        public double totReturns = 0;

Public, og double, ok double kan antage højere værdier end long... men hvis der er brug for det har vi jo alligevel et uløseligt problem vil jeg mene...

Restart skal vel lige kaldes fra Constructoren... ellers vil en alm. brug af next resultere i fejl... (man kan naturligvis kalde retart externet, men vil ikke mene det burde være et krav)...

Revers metoden kan fjernes og erstattes med Array.Reverse...

sted a:
//reverse(position + 1);
Array.Reverse(this.sub, (position + 1), sub.Length - (position + 1));
sted b:
//reverse(incr + 1);
Array.Reverse(this.sub, (incr + 1), sub.Length - (incr + 1));

        private void restart()
        {
            totReturns = 0;
            for (int i = 0; i < collect.Count; i++)
                sub[i] = i;
            firstTime = true;
            totReturns = 0;
        }

hvorfor bliver totReturns sat 2 gange??

Det hjælper jo af og til at ryde op i koden...

Angående fields, der er sat public i koden jeg hentede, så er jeg selv allergisk over for public fields, så jeg har ændret dem til private og lavet en getter på sub. Det er meget smart under test at kunne se indeks på den permutation man får returneret og den står i sub.

Jeg har ikke kigget så indgående på reverse metoden, men forfatteren skriver jo selv at "this just puts the tail in order.  We need not do a full sort since we know the elements are in reverse order.". Ved ikke om hans reverse benytter samme antal iterationer som en generic sort, men jeg har ikke følt mig stødt over hans argumentation.

Allan

Det har ikke noget med sort at gøre hans reverse... men derimod Reverse... dvs.

at 0,1,2,3 bliver til 3,2,1,0... men virker lidt omsonst at lave noget selv som frameworket allerede tilbyder... dog gør man det jo typisk fordi man ikke ved at frameworket tilbyder det...

Derfor gør den nødagtig det samme som det je viste du kunne erstatte den med, med den undtagelse at hans er fra et start index og arrayet ud, med Array.Reverse kan man også give et slut index, og så kun reverse midten... men som sagt... det er en metode mindre i klassen...

Sidst men ikke midst... sub skal da vel slet ikke have en proterty... som jeg ser det er det et intærnt indices array... det får du aldrig brug for at kende uden for klassen normalt... derfor ville jeg bare have det som et private field uden en property til det...

hov... læste ikke hele det du skrev kan jeg se :P

Ja til test er det meget rart at se... sørg få du ikke ender med at kunne redigere i den ude fra... det kunne fucke pænt meget op...