N-de permutatie vinden zonder anderen te berekenen

Gegeven een array van N-elementen die de permutatie-atomen voorstellen, is er een algoritme zoals dat:

function getNthPermutation( $atoms, $permutation_index, $size )

waarbij $ atomen de reeks elementen is, is $ permutation_index de index van de permutatie en $ grootte de grootte van de permutatie.

Bijvoorbeeld:

$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );

echo implode( ', ', $perm )."\n";

Zou afdrukken:

B, A

Zonder elke permutatie te berekenen tot $ permutation_index?

Ik hoorde iets over factoradische permutaties, maar elke implementatie die ik heb gevonden geeft als resultaat een permutatie met dezelfde grootte van V, wat niet mijn geval is.

Bedankt.

36
stel je voor dat je elke permutatie van N-elementen afdrukt met zijn iteratieteller (permutatie 0, permutatie 1, permutatie 2, ...) ... ik wil de n-de permutatie.
toegevoegd de auteur Simone Margaritelli, de bron
ik geef niet om het sorteren van de permutaties, iedereen zal het werk doen :)
toegevoegd de auteur Simone Margaritelli, de bron
als je niet om de bestelling geeft, kun je gewoon ELKE permutatie kiezen van de grootte $ -grootte die je leuk vindt. wil je deze functie elke keer meerdere keren bellen met een andere index?
toegevoegd de auteur galchen, de bron
maar wat bepaalt de volgorde van de permutatie? ik bedoel, permutatie met index 0 kan een van de vormen zijn
toegevoegd de auteur galchen, de bron
wat bedoel je met de index van de permutatie?
toegevoegd de auteur galchen, de bron

7 antwoord

Zoals vermeld door RickyBobby, moet je bij het overwegen van de lexicografische volgorde van permutaties de factoriële ontbinding in je voordeel gebruiken.

Vanuit praktisch oogpunt is dit hoe ik het zie:

  • Voer een soort van Euclidische indeling uit, behalve dat u dit doet met factialummers, beginnend met (n-1)! , (n-2)! , en dus op.
  • Houd de quotiënten in een array. Het i -de quotiënt moet een getal zijn tussen 0 en ni-1 inclusief, waarbij i van 0 tot n-1 .
  • Deze array is uw permutatie. Het probleem is dat elk quotiënt niet om eerdere waarden geeft, dus u moet ze aanpassen. Meer expliciet moet u elke waarde even vaak verhogen als er eerdere waarden zijn die lager of gelijk zijn.

De volgende C-code zou u een idee moeten geven van hoe dit werkt ( n is het aantal vermeldingen en i is de index van de permutatie):

/**
 * @param n The number of entries
 * @param i The index of the permutation
 */
void ithPermutation(const int n, int i)
{
   int j, k = 0;
   int *fact = (int *)calloc(n, sizeof(int));
   int *perm = (int *)calloc(n, sizeof(int));

  //compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

  //compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = i/fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

  //readjust values to obtain the permutation
  //start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

  //print permutation
   for (k = 0; k < n; ++k)
      printf("%d ", perm[k]);
   printf("\n");

   free(fact);
   free(perm);
}

Bijvoorbeeld, ithPermutation (10, 3628799) print, zoals verwacht, de laatste permutatie van tien elementen:

9 8 7 6 5 4 3 2 1 0
41
toegevoegd
+1 thx Felix voor de implementatie :)
toegevoegd de auteur Ricky Bobby, de bron
Dat was precies de implementatie die ik zocht, het 'n' argument is de sleutel ... heel erg bedankt :)
toegevoegd de auteur Simone Margaritelli, de bron
De methode die hier wordt gebruikt om de factoradic/lehmer-code te krijgen (maakt gebruik van berekende faculteiten en slaat quotiënten op die niet als resten worden gebruikt) verschilt van de methode die wordt beschreven op de Wikipedia-pagina van Factoradic net iets boven het gedeelte Voorbeelden. De uitvoer zoals ik die heb getest is hetzelfde, maar ik vind de laatste methode eenvoudiger. Niettemin heeft jouw voorbeeld me ook geholpen het concept beter te begrijpen.
toegevoegd de auteur konsolebox, de bron

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.

Decision tree for permutations of 4 elements

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.

Decision three for number 27 in decimal

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));
}
25
toegevoegd

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.

14
toegevoegd
@SimoneMargaritelli Wat bedoel je met? wil je een permutatie van één deelverzameling van je originele set elementen?
toegevoegd de auteur Ricky Bobby, de bron
ik ben al op de hoogte van het factorieserienummersysteem, maar ik kan geen implementatie vinden waarbij de grootte van de uitvoerpermutatie niet hetzelfde is als de oorspronkelijke vector van items.
toegevoegd de auteur Simone Margaritelli, de bron
Je zou eigenlijk O (n lg lg U) kunnen doen met behulp van vEB-bomen, omdat U = n. Ik vraag me af wat de onderste grens is ??
toegevoegd de auteur dhruvbird, de bron

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

7
toegevoegd
Deze oplossing is waarschijnlijk de snelste omdat u geen array-splitsing (of elementverwijdering) hoeft uit te voeren en er geen geneste for-lussen +1 zijn.
toegevoegd de auteur James, de bron

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)

4
toegevoegd
Wat is er gebeurd als uw lijst dubbele tekens bevat? Het produceert verkeerd resultaat.
toegevoegd de auteur Sonu Kumar, de bron

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.

1
toegevoegd
Oké, je hebt gelijk, wil je dit horen? :) Het was gewoon een misverstand, doe het rustig joh;)
toegevoegd de auteur Simone Margaritelli, de bron
ik denk dat het nogal voor de hand liggend was, omdat ik zei '... zonder elke permutatie te berekenen ...' ...
toegevoegd de auteur Simone Margaritelli, de bron
als ik dit vraag is omdat ik het al heb getest met vooraf gedefinieerde permutaties ...
toegevoegd de auteur Simone Margaritelli, de bron
Kan het niet weerstaan. Een algoritme dat vooraf gedefinieerde permutaties gebruikt, berekent geen permutaties. (Ik ben alleen hier omdat ik de vraag en de andere antwoorden nuttig vond).
toegevoegd de auteur dansalmo, de bron
+1 om Simone niet het antwoord te geven op de vraag die hij wilde stellen, maar het antwoord op de vraag die hij eigenlijk stelde.
toegevoegd de auteur Patrick87, de bron
sorry, mijn paranormale krachten moeten me vandaag teleurstellen - dat of je hebt die informatie in een heel kleine tekst in je vraag gezet.
toegevoegd de auteur Chris Browne, de bron
Je hebt eigenlijk gezegd "zonder elke permutatie te berekenen tot $ permutation_index", wat niet hetzelfde is als "zonder elke permutatie te berekenen". Dat is de eerste keer dat ik iemand ooit zelf heb zien citeren uit de context!
toegevoegd de auteur Chris Browne, de bron
Aha, je hebt me te slim af geweest met de oude "kalmte" -truc. Elke reactie die ik nu schrijf, zal boos klinken, wat mijn reputatie negatief zou kunnen beïnvloeden! Laat maar, ik ben toch niet zo druk met "winnende argumenten", meer geïnteresseerd in daadwerkelijke vooruitgang.
toegevoegd de auteur Chris Browne, de bron
Dit is een twee jaar oud antwoord, de andere antwoorden op deze vraag zijn volkomen bevredigend, dus ik zie het niet nodig om mijn eigen te bewerken (ik zou geneigd zijn om het eenvoudigweg te verwijderen). Mijn houding tegenover ondervraging zou tegenwoordig veel nederiger en vergevingsgezinder zijn. Ik denk dat ik gewoon een slechte dag had op 27 oktober 2011.
toegevoegd de auteur Chris Browne, de bron

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; }

       //************************************************************************
        /// 
/// Return the permutation relative to the index received, according to /// _sortedValues. /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception. ///
 
        /// 
        /// 
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;
            }
        }

       //************************************************************************
        /// 
/// Calc the index, relative to _sortedValues, of the permutation received /// as argument. Returned index is 0 based. ///
 
        /// 
        /// 
        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;
        }

       //************************************************************************
    }
}
0
toegevoegd