N-de permutatie vinden zonder anderen te berekenen

Hier is een oplossing waarmee u de grootte van de permutatie kunt selecteren. Afgezien van het kunnen genereren van alle permutaties van 10 elementen, kan het bijvoorbeeld permutaties van paren van 10 elementen genereren. Het permuteert ook lijsten van willekeurige objecten, niet alleen gehele getallen.

Dit is PHP, maar er is ook JavaScript en Haskell impementation.

function nth_permutation($atoms, $index, $size) {
    for ($i = 0; $i < $size; $i++) {
        $item = $index % count($atoms);
        $index = floor($index/count($atoms));
        $result[] = $atoms[$item];
        array_splice($atoms, $item, 1);
    }
    return $result;
}

Gebruik voorbeeld:

for ($i = 0; $i < 6; $i++) {
    print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
// => AB, BA, CA, AC, BC, CB

Hoe werkt het?

Er zit een heel interessant idee achter. Laten we de lijst A, B, C, D nemen. We kunnen een permutatie construeren door er elementen uit te trekken, zoals uit een pak kaarten. Aanvankelijk kunnen we een van de vier elementen tekenen. Dan een van de drie overgebleven elementen, enzovoort, tot we uiteindelijk niets meer hebben.

Hier is een mogelijke volgorde van keuzes. Vanaf de top nemen we het derde pad, dan het eerste, het tweede en ten slotte het eerste. En dat is onze permutatie # 13.

Denk na over hoe je, gezien deze reeks keuzes, op algoritmisch nummer dertien zou komen. Keer vervolgens uw algoritme om, en zo kunt u de volgorde van een geheel getal reconstrueren.

Laten we proberen een algemeen schema te vinden voor het verpakken van een reeks keuzes in een geheel getal zonder redundantie, en het uitpakken.

Een interessant schema wordt decimaal nummersysteem genoemd. "27" kan worden gezien als het kiezen van pad # 2 van de 10 en vervolgens het kiezen van pad # 7 van de 10.

Maar elk cijfer kan alleen keuzes coderen uit 10 alternatieven. Andere systemen met een vaste radix, zoals binair en hexadecimaal, kunnen ook alleen reeksen keuzes uit een vast aantal alternatieven coderen. We willen een systeem met een variabele radix, een soort tijdseenheden, "14:05:29" is uur 14 van 24, minuut 5 van 60, tweede 29 van 60.

Wat als we generieke nummer-naar-string en string-naar-nummer-functies gebruiken en hen voor de gek houden met het gebruik van gemengde radixen? In plaats van een enkele radix, zoals parseInt ('beef') , 16) en (48879) .toString (16) , nemen ze een radix per cijfer.

function pack(digits, radixes) {
    var n = 0;
    for (var i = 0; i < digits.length; i++) {
        n = n * radixes[i] + digits[i];
    }
    return n;
}

function unpack(n, radixes) {
    var digits = [];
    for (var i = radixes.length - 1; i >= 0; i--) {
        digits.unshift(n % radixes[i]);
        n = Math.floor(n/radixes[i]);
    }
    return digits;
}

Werkt dat zelfs?

// Decimal system
pack([4, 2], [10, 10]);//=> 42

// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]);//=> 42

// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]);//=> 42

En nu achteruit:

unpack(42, [10, 10]);//=> [4, 2]

unpack(42, [5, 4, 3, 2, 1]);//=> [1, 3, 0, 0, 0]

Dit is zo mooi. Laten we nu dit parametrische nummersysteem toepassen op het probleem van permutaties. We overwegen lengte 2 permutaties van A, B, C, D . Wat is het totale aantal van hen? Laten we eens kijken: eerst tekenen we een van de 4 items, dan een van de resterende 3, dat is 4 * 3 = 12 manieren om 2 items te tekenen. Deze 12 manieren kunnen worden ingepakt in gehele getallen [0..11]. Laten we dus doen alsof we ze al hebben ingepakt en proberen uit te pakken:

for (var i = 0; i < 12; i++) {
    console.log(unpack(i, [4, 3]));
}

// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]

Deze getallen vertegenwoordigen keuzes, geen indexen in de oorspronkelijke array. [0, 0] betekent niet dat je A, A gebruikt, dit betekent dat je item # 0 van A, B, C, D (dat is A) en dan item # 0 uit de resterende lijst B, C, D (dat is B). En de resulterende permutatie is A, B .

Nog een voorbeeld: [3, 2] betekent item # 3 van A, B, C, D (dat is D) en vervolgens item # 2 uit de resterende lijst A, B, C (dat is C). En de resulterende permutatie is D, C .

Deze toewijzing wordt Lehmer code genoemd. Laten we al deze Lehmer-codes in kaart brengen voor permutaties:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

Dat is precies wat we nodig hebben. Maar als u de functie uitpakken bekijkt, merkt u dat deze cijfers van rechts naar links produceert (om de acties van pack om te keren). De keuze uit 3 wordt uitgepakt voordat de keuze uit 4 wordt gemaakt. Dat is jammer, omdat we willen kiezen uit 4 elementen voordat we uit 3 kiezen. Zonder dit te kunnen doen, moeten we eerst de Lehmer-code berekenen, deze stapelen in een tijdelijke array, en pas het vervolgens toe op de reeks items om de daadwerkelijke permutatie te berekenen.

Maar als we ons niet druk maken om de lexicografische volgorde, kunnen we doen alsof we uit 3 elementen willen kiezen voordat we uit 4 kiezen. Dan komt de keuze uit 4 eerst uit uitpakken . Met andere woorden, we gebruiken uitpakken (n, [3, 4]) in plaats van uitpakken (n, [4, 3]) . Met deze truc kan het volgende cijfer van de Lehmer-code worden berekend en onmiddellijk worden toegepast op de lijst. En dat is precies hoe nth_permutation() werkt.

Een laatste ding dat ik wil vermelden is dat unpack (i, [4, 3]) nauw verwant is met het factoriesysteem. Kijk nogmaals naar die eerste boom, als we permutaties van lengte 2 willen zonder duplicaten, kunnen we elke tweede permutatie-index overslaan. Dat geeft ons 12 permutaties van lengte 4, die op lengte 2 kunnen worden bijgesneden.

for (var i = 0; i < 12; i++) {
    var lehmer = unpack(i * 2, [4, 3, 2, 1]);//Factorial number system
    console.log(lehmer.slice(0, 2));
}

Het hangt af van de manier waarop u uw permutaties "sorteert" (bijvoorbeeld lexicografische volgorde).

Een manier om dit te doen is het factoriesysteem , het geeft u een bijectie tussen [0, n!] en alle permutaties.

Dan voor elk aantal i in [0, n!] Kun je de ith-permutatie berekenen zonder de anderen te berekenen.

Deze faculteit is gebaseerd op het feit dat elk getal tussen [0 en n!] Geschreven kan worden als:

SUM( ai.(i!) for i in range [0,n-1]) where ai 

(het is vergelijkbaar met base-decompositie)

for more information on this decomposition, have a look at this thread : https://math.stackexchange.com/questions/53262/factorial-decomposition-of-integers

hoop dat het helpt

Zoals vermeld in dit Wikipedia-artikel komt deze benadering overeen met het berekenen van de lehmer code :

Een voor de hand liggende manier om permutaties van n te genereren, is door waarden te genereren   de Lehmer-code (mogelijk met behulp van het facultatieve getalsysteem   vertegenwoordiging van gehele getallen tot n!), en zet die in de   overeenkomstige permutaties. Echter, de laatste stap, terwijl   rechttoe rechtaan, is moeilijk efficiënt te implementeren, omdat het vereist   n bewerkingen elk van selectie uit een reeks en verwijderen ervan,   op een willekeurige positie; van de voor de hand liggende afbeeldingen van de   volgorde als een array of een gekoppelde lijst, beide vereisen (voor verschillende   redenen) over n2/4-bewerkingen om de conversie uit te voeren. Met n   waarschijnlijk vrij klein (vooral als generatie van alles   permutaties is nodig), dat is niet al te veel een probleem, maar het   blijkt dat zowel voor willekeurige als voor systematische generatie er zijn   eenvoudige alternatieven die aanzienlijk beter presteren. Om deze reden is het   lijkt niet nuttig, hoewel zeker mogelijk, om een ​​special te gebruiken   datastructuur die het uitvoeren van de conversie van Lehmer mogelijk zou maken   code voor permutatie in O (n log n) tijd.

Dus het beste wat je kunt doen voor een set van n elementen is O (n ln (n)) met een aangepaste gegevensstructuur.

Hier is een algoritme om in lineaire tijd te converteren tussen permutaties en rangen. De rangorde die het gebruikt, is echter niet lexicografisch. Het is raar, maar consistent. Ik ga twee functies geven, een die converteert van een rang naar een permutatie, en een die de inverse doet.

Ten eerste om te unrank (ga van rang naar permutatie)

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

Volgende om te rangschikken:

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q[s], q[n-1])
  return s + n * rank(n-1, p, q)
end

De looptijd van beide is O (n).

There's a nice, readable paper explaining why this works: Ranking & Unranking Permutations in Linear Time, by Myrvold & Ruskey, Information Processing Letters Volume 79, Issue 6, 30 September 2001, Pages 281–284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey. pdf

Hier is een korte en zeer snelle (lineair in het aantal elementen) oplossing in python, werkend voor elke lijst van elementen (de 13 eerste letters in het onderstaande voorbeeld):

from math import factorial

def nthPerm(n,elems):#with n from 0
    if(len(elems) == 1):
        return elems[0]
    sizeGroup = factorial(len(elems)-1)
    q,r = divmod(n,sizeGroup)
    v = elems[q]
    elems.remove(v)
    return v + ", " + ithPerm(r,elems)

Voorbeelden:

letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m']

ithPerm(0,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, k, l, m
ithPerm(4,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, m, k, l
ithPerm(3587542868,letters[:]) #--> h, f, l, i, c, k, a, e, g, m, d, b, j

Opmerking: ik geef letters [:] (een kopie van letters ) en geen letters omdat de functie zijn parameter elems wijzigt (verwijdert gekozen element)

Als u alle permutaties in het geheugen opslaat, bijvoorbeeld in een array, moet u ze één voor één in O (1) tijd kunnen verwijderen.

Dit betekent dat je alle permutaties moet opslaan, dus als het berekenen van alle permutaties een onoverkomelijk lange tijd vergt, of als het opslaan ervan een onbetrouwbaar grote ruimte in beslag neemt, dan is dit misschien geen oplossing.

Mijn suggestie zou zijn om het toch te proberen en terug te komen als het te groot/langzaam is - het heeft geen zin om naar een "slimme" oplossing te zoeken als een naïef iemand het werk zal doen.

Het is berekenbaar. Dit is een C# -code die het voor u doet.

using System;
using System.Collections.Generic;

namespace WpfPermutations
{
    public class PermutationOuelletLexico3
    {
       //************************************************************************
        private T[] _sortedValues;

        private bool[] _valueUsed;

        public readonly long MaxIndex;//long to support 20! or less 

       //************************************************************************
        public PermutationOuelletLexico3(T[] sortedValues)
        {
            if (sortedValues.Length <= 0)
            {
                throw new ArgumentException("sortedValues.Lenght should be greater than 0");
            }

            _sortedValues = sortedValues;
            Result = new T[_sortedValues.Length];
            _valueUsed = new bool[_sortedValues.Length];

            MaxIndex = Factorial.GetFactorial(_sortedValues.Length);
        }

       //************************************************************************
        public T[] Result { get; private set; }

       //************************************************************************
        /// 

 
        /// 

        /// 

Value is not used as inpu, only as output. Re-use buffer in order to save memory
        /// 
        public void GetValuesForIndex(long sortIndex)
        {
            int size = _sortedValues.Length;

            if (sortIndex < 0)
            {
                throw new ArgumentException("sortIndex should be greater or equal to 0.");
            }

            if (sortIndex >= MaxIndex)
            {
                throw new ArgumentException("sortIndex should be less than factorial(the lenght of items)");
            }

            for (int n = 0; n < _valueUsed.Length; n++)
            {
                _valueUsed[n] = false;
            }

            long factorielLower = MaxIndex;

            for (int index = 0; index < size; index++)
            {
                long factorielBigger = factorielLower;
                factorielLower = Factorial.GetFactorial(size - index - 1); // factorielBigger/inverseIndex;

                int resultItemIndex = (int)(sortIndex % factorielBigger/factorielLower);

                int correctedResultItemIndex = 0;
                for(;;)
                {
                    if (! _valueUsed[correctedResultItemIndex])
                    {
                        resultItemIndex--;
                        if (resultItemIndex < 0)
                        {
                            break;
                        }
                    }
                    correctedResultItemIndex++;
                }

                Result[index] = _sortedValues[correctedResultItemIndex];
                _valueUsed[correctedResultItemIndex] = true;
            }
        }

       //************************************************************************
        /// 

 
        /// 

        /// 
        public long GetIndexOfValues(T[] values)
        {
            int size = _sortedValues.Length;
            long valuesIndex = 0;

            List valuesLeft = new List(_sortedValues);

            for (int index = 0; index < size; index++)
            {
                long indexFactorial = Factorial.GetFactorial(size - 1 - index);

                T value = values[index];
                int indexCorrected = valuesLeft.IndexOf(value);
                valuesIndex = valuesIndex + (indexCorrected * indexFactorial);
                valuesLeft.Remove(value);
            }
            return valuesIndex;
        }

       //************************************************************************
    }
}