Başkalarını hesaplamadan n-inci permütasyonu bulma

Permütasyon atomlarını temsil eden bir dizi N öğesi verildiğinde, şöyle bir algoritma var:

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

$ atoms öğelerin dizisidir; $ permutation_index , permütasyonun dizinidir ve $ size , permütasyonun boyutudur.

Örneğin:

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

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

Yazdırmak:

B, A

$ Permutation_index'e kadar her permütasyon hesaplanmadan mı?

Factoradic permütasyonlar hakkında bir şeyler duydum, fakat bulduğum her uygulama, aynı büyüklükteki V ile bir permütasyon olarak sonuç veriyor, ki bu benim durumum değil.

Teşekkürler.

36
Yineleme sayacı (permütasyon 0, permütasyon 1, permütasyon 2, ...) ile N öğelerinin her bir permütasyonunu yazdırdığınızı hayal edin ... n-th permütasyonunu istiyorum.
katma yazar Simone Margaritelli, kaynak
permütasyonların sıralamasını umursamıyorum, herhangi bir iş yapacağım :)
katma yazar Simone Margaritelli, kaynak
Siparişi umursamıyorsanız, istediğiniz boyutun boyutunun HERHANGİ bir permütasyonunu seçebilirsiniz. Bu işlevi her defasında farklı bir dizinle birkaç kez çağırmak ister misiniz?
katma yazar galchen, kaynak
ama permütasyonun sırasını ne belirler? Yani, endeks 0 ile permütasyon herhangi bir form olabilir
katma yazar galchen, kaynak
permütasyon indeksi ne demek istiyorsun?
katma yazar galchen, kaynak

7 cevap

RickyBobby tarafından belirtildiği gibi, sözcüklerin alfabetik sıralaması göz önünde bulundurulduğunda, faktöriyel ayrışmayı sizin yararınıza kullanmalısınız.

Pratik bir bakış açısıyla, bunu nasıl görüyorum:

  • Euclidian bölümü gerçekleştirin, ancak fakültatif sayılarla (n-1)! , (n-2)! ile başlayarak bunu yapın. üzerinde.
  • Bölümleri bir dizide tutun. i .sayısı 0 ve ni-1 arasındaki bir sayı olmalıdır; burada i < kodu> 0 - n-1 .
  • .
  • Bu dizi , permütasyonunuz . Sorun, her bir bölümün önceki değerleri önemsememesidir, bu yüzden bunları ayarlamanız gerekir. Daha açık bir şekilde, daha düşük veya eşit olan önceki değerler olduğu için her değeri birçok kez artırmanız gerekir.

Aşağıdaki C kodu, bunun nasıl çalıştığına dair bir fikir vermelidir ( n giriş sayısıdır ve i , permütasyonun indisidir):

/**
 * @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);
}

Örneğin, ithPermutation (10, 3628799) beklendiği gibi, on öğenin son permütasyonu yazdırır:

9 8 7 6 5 4 3 2 1 0
41
katma
Uygulama için +1 thx Felix :)
katma yazar Ricky Bobby, kaynak
Tam olarak aradığım uygulama buydu, 'n' argümanı anahtar ... teşekkürler soooo çok :)
katma yazar Simone Margaritelli, kaynak
Factoradic/lehmer kodunu elde etmek için burada kullanılan yöntem (hesaplanan faktörler ve kalan kısımları depolar), Factoradic , sadece Örnekler bölümünün biraz üstünde. Test ettiğim çıktı aynı olsa da, ikinci yöntemi daha basit buluyorum. Yine de örneğiniz aynı zamanda kavramı daha iyi anlamama yardımcı oldu.
katma yazar konsolebox, kaynak

İşte, permütasyonun boyutunu seçmeye yarayan bir çözüm. Örneğin, 10 elementin tüm permütasyonlarını üretebilmekten ayrı olarak, 10 eleman arasında çiftlerin permütasyonlarını üretebilir. Ayrıca sadece tamsayılar değil, keyfi nesnelerin listelerine izin verir.

Bu PHP'dir, ancak ayrıca JavaScript ve 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;
}

Kullanım örneği:

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

Nasıl çalışır?

Arkasında çok ilginç bir fikir var. A, B, C, D listesini alalım. Bir kart destesi gibi ondan elemanlar çizerek bir permütasyon oluşturabiliriz. Başlangıçta dört elementten birini çizebiliriz. Sonra kalan üç elementten biri ve benzeri, sonunda nihayet hiçbir şeyimiz kalmadı.

Decision tree for permutations of 4 elements

İşte olası bir seçim sırası. En baştan başlayarak üçüncü yolu, sonra birinciyi, ikinciyi ve nihayetinde ilkini alıyoruz. Ve bu bizim permütasyonumuz # 13.

Bu seçimler sırası göz önüne alındığında, algoritmik olarak on üç numaraya nasıl ulaşacağınızı düşünün. Ardından algoritmanızı tersine çevirin, böylece diziyi bir tamsayıdan nasıl yeniden yapılandırabilirsiniz.

Bir dizi seçimin fazlalık olmadan bir tam sayıya paketlenmesi ve paketin açılması için genel bir şema bulmaya çalışalım.

Bir ilginç şema ondalık sayı sistemi denir. "27", 10'un 2 numaralı yolunu seçip, 10'uncu yoldan # 7 yolunu seçebilir.

Decision three for number 27 in decimal

Ancak her rakam sadece 10 alternatif arasından seçim yapabilir. İkili ve onaltılı gibi sabit bir çapa sahip diğer sistemler de, yalnızca belirli sayıda seçenek arasından seçim dizilerini kodlayabilir. Değişken bir çapa sahip bir sistem istiyoruz, benzer bir zaman birimi, "14:05:29" saat 14'ten 24'e, dakika 5'ten 60'a, ikinci 29'dan 60'a.

Ya nümerik sayıdan dizeye ve dizeden sayıya işlevler alırsak ve bunları karma yarıçapları kullanarak kandırırsak? parseInt ('beef') gibi tek bir yarıçapı almak yerine , 16) ve (48879) .toString (16) , her bir basamağa bir adet radix alacaktır.

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

Bu bile işe yarıyor mu?

// 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

Ve şimdi geriye doğru:

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

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

Bu çok güzel. Şimdi bu parametrik sayı sistemini permütasyon problemine uygulayalım. A, B, C, D uzunluk 2 permütasyonlarını dikkate alacağız. Toplam sayı nedir? Bakalım: önce 4 öğeden birini, sonra kalan 3'lerden birini çiziyoruz, bu da 4 * 3 = 12 2 öğe çizmenin yolları. Bu 12 yol tamsayılar halinde paketlenebilir [0..11]. Öyleyse, onları zaten paketlediğimizi ve paketini açmayı deneyelim:

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]

Bu sayılar, orijinal dizideki dizinleri değil, seçimleri temsil eder. [0, 0], A, A almayı kastetmez, A, B, C, D öğelerinden # bu demektir. 0 kalan listeden B, C, D (bu B). Ve ortaya çıkan permütasyon A, B .

Başka bir örnek: [3, 2] A, B, C, D öğesinden # (bu D) ve # 2 numaralı öğeden kalan A, B, C <�öğelerinden # 3 almak anlamına gelir./code> (bu C). Ve ortaya çıkan permütasyon D, C .

Bu eşleme, Lehmer kodu olarak adlandırılır. Tüm bu Lehmer kodlarını permütasyonlara eşleyelim:

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

Tam da ihtiyacımız olan şey bu. Ancak unpack fonksiyonuna bakarsanız, sağdan sola doğru rakamlar ürettiğini fark edeceksiniz ( pack eylemlerini tersine çevirmek için). 3'ten seçim 3'üncü seçimden önce açılır. Bu talihsiz bir durumdur, çünkü biz 3'ü seçmeden önce 4 element arasından seçim yapmak isteriz. Bunu yapmadan yapabilmek için, önce Lehmer kodunu hesaplamalıyız, bunu geçici bir diziye biriktirmeliyiz, ve sonra gerçek permütasyonu hesaplamak için öğeleri dizisine uygulayın.

Ancak, sözlükbilimsel düzeni umursamazsak, 4'ten seçim yapmadan önce 3 öğeden birini seçmek istediğimizi iddia edebiliriz. Sonra 4'ten seçim, önce unpack 'dan çıkar. Başka bir deyişle, unpack (n, [4, 3]) yerine unpack (n, [3, 4]) komutunu kullanacağız. Bu hile, Lehmer kodunun bir sonraki basamağını hesaplamaya ve derhal listeye uygulamanıza izin verir. Ve tam olarak bu nasıl nth_permutation() çalışır.

Bahsetmek istediğim son bir şey, unpack (i, [4, 3]) 'ün faktör sayı sistemi ile yakından ilişkili olmasıdır. Tekrar ilk ağaçlara bakalım, eğer uzunluk 2'nin kopyaları olmaksızın permütasyonlar istiyorsak, her ikinci permütasyon indeksini atlayabiliriz. Bu bize uzunluk 2'ye kadar kesilebilen uzunluk 4'ün 12 permütasyonunu verecektir.

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
katma

Bu sizin permütasyonlarınızı "sıralamanıza" bağlıdır (örneğin sözlüksel sıra).

Bunu yapmanın bir yolu faktöriyel sayı sistemi , size [0, n!] ve tüm permütasyonlar.

Sonra [0, n!] 'De herhangi bir sayı i için, başkalarını hesaplamadan, onun permütasyonunu hesaplayabilirsiniz.

Bu faktör yazımı, [0 ve n!] Arasındaki herhangi bir sayıyı şöyle yazabilir:

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

(temel ayrışmaya oldukça benzer)

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

Umarım yardımcı olur


Bu wikipedia makalesinde belirtildiği gibi, bu yaklaşım lehmer kodu :

n'nin permütasyonlarını oluşturmanın bariz bir yolu,   Lehmer kodu (muhtemelen faktör sayı sistemini kullanarak   n'ye kadar tamsayıların gösterimi) ve bunları   karşılık gelen permütasyonlar. Ancak, ikinci adım   basittir, verimli bir şekilde uygulanması zordur, çünkü gerekli   n işlemlerin her birinin bir diziden seçilmesi ve silinmesi,   keyfi bir pozisyonda; açık temsillerin   Bir dizi veya bağlantılı bir liste olarak dizisi, her ikisi de gerektirir (farklı için)   nedenleri) dönüşüm gerçekleştirmek için n2/4 işlemleri. N ile   oldukça küçük olması muhtemeldir (özellikle tümünün üretimi   permütasyonlar gereklidir) çok fazla problem değil, ama   hem rastlantısal hem de sistematik jenerasyon için var.   Oldukça iyi olan basit alternatifler. Bu sebepten dolayı   kesinlikle mümkün olsa da, yararlı bir işe yaramaz   Lehmer'den dönüşüm gerçekleştirmeyi sağlayan veri yapısı   O (n log n) saatinde permütasyon kodu.

Dolayısıyla, bir dizi n elemanı için yapabileceğiniz en iyi şey, uyarlanmış bir veri yapısına sahip olan O (n ln (n)) 'dir.

14
katma
@SimoneMargaritelli Ne demek istiyorsun? Orijinal öğe grubunuzun bir alt kümesinin bir permütasyonunu ister misiniz?
katma yazar Ricky Bobby, kaynak
Faktöriyel sayı sisteminin zaten farkındayım, ancak çıktı permütasyonunun büyüklüğünün, öğelerin ilk vektörünün aynı olmadığı bir uygulama bulamıyorum.
katma yazar Simone Margaritelli, kaynak
U = n olduğundan, vEB ağaçları kullanarak aslında O (n lg lg U) yapabilirsiniz. Alt sınırın ne olduğunu merak ediyorum?
katma yazar dhruvbird, kaynak

Burada, doğrusal zamandaki permütasyonlar ve sıralar arasında dönüşme algoritması var. Ancak, kullandığı sıralama sözlüksel değildir. Tuhaf, ama tutarlı. Ben bir ranktan bir permüse ve tersi olana dönüşen iki fonksiyon vereceğim.

Öncelikle, unrank (rütbeden permüse gitmek)

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

Sırada, sıralamak için:

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

Her ikisinin de çalışma süresi 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
katma
Bu çözüm muhtemelen en hızlıdır çünkü dizi ekleme (veya öğe kaldırma) yapmanız gerekmez ve döngüler +1 için yuvalanmamıştır.
katma yazar James, kaynak

Burada python'da kısa ve çok hızlı (element sayısındaki doğrusal) çözüm, herhangi bir eleman listesi için çalışır (aşağıdaki örnekte yer alan 13 ilk harf):

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)

Örnekler:

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

Not: elems parametresini değiştirdiği için letters [:] ( letters kopyasının bir kopyasını) veririm.

4
katma
Listeniz çift karakterli karakterler içeriyorsa ne oldu? Yanlış sonuç üretiyor.
katma yazar Sonu Kumar, kaynak

Tüm permütasyonları bellekte (örneğin bir dizide) saklarsanız, O (1) saatte birer birer geri getirebilmeniz gerekir.

Bu, tüm permütasyonları depolamanız gerektiği anlamına gelir, bu nedenle tüm permütasyonların hesaplanması uzun bir süre gerektiriyorsa veya bunları depolamak, büyük ölçüde geniş bir alan gerektiriyorsa, bu bir çözüm olmayabilir.

Benim önerim yine de onu denemek ve çok büyük/yavaşsa geri dönmektir - eğer saf bir kişi işi yapacaksa “akıllı” bir çözüm aramak için hiçbir nokta yoktur.

1
katma
Tamam haklısın, duymak istediğin bu mu? :) Sadece bir yanlış anlama, kolay ahbap;)
katma yazar Simone Margaritelli, kaynak
"Her permütasyon hesaplanmadan ..." dediğimden beri çok açık olduğunu düşünüyorum ...
katma yazar Simone Margaritelli, kaynak
Bunu sorsam, önceden hesaplanmış permütasyonlarla test ettiğim için ...
katma yazar Simone Margaritelli, kaynak
Dayanamıyorum. Önceden hesaplanmış permütasyonları kullanan bir algoritma, herhangi bir permütasyon hesaplamamaktadır. (Ben sadece buradayım çünkü soru ve diğer cevapları faydalı buldum).
katma yazar dansalmo, kaynak
Simone'a vermek istediği +1 sorusunu sormak istemediğini, ancak sorduğu sorunun cevabını sordu.
katma yazar Patrick87, kaynak
Özür dilerim, psişik güçlerim bugün bana başarısız olmalı - ya da bu bilgiyi sorunuzda çok küçük bir metne koydunuz.
katma yazar Chris Browne, kaynak
Aslında, "her permütasyon hesaplanmadan" ile aynı olan "permutation_index'e kadar her permütasyon hesaplanmadan" ifadesini kullandınız. Şimdiye kadar birileri ilk kez kendilerini bağlam dışı gördüğümü gördüm!
katma yazar Chris Browne, kaynak
Aha, eski "sakin" hilesiyle beni reddettin. Şimdi yazdığım herhangi bir yanıt, benim itibarımı olumsuz yönde etkileyecek şekilde sinirli olacaktır! Asla boşuna, aslında "ilerleme argümanlar" hakkında çok fazla uğraşmadım, gerçek ilerlemeyle daha çok ilgileniyorum.
katma yazar Chris Browne, kaynak
Bu iki yıllık bir cevaptır, bu sorunun diğer cevapları mükemmel bir şekilde tatmin edicidir, bu yüzden kendimi düzenlemem gerekmediğini görüyorum (eğer bir şey varsa, sadece onu silmek eğilimindeydim). Sorgulanmaya karşı tavrım, bu günlerde kayıt için çok daha alçakgönüllü ve affedici olacaktır. 27 Ekim 2011'de kötü bir gün geçirdiğimi düşünüyorum.
katma yazar Chris Browne, kaynak

Hesaplanabilir. Bu sizin için C# kodudur.

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
katma