Permutasi cepat -> angka -> algoritma pemetaan permutasi

Saya memiliki n elemen. Sebagai contoh, katakanlah, 7 elemen, 1234567. Saya tahu ada 7! = 5040 kemungkinan permutasi dari 7 elemen ini.

Saya ingin algoritme cepat yang terdiri dari dua fungsi:

f (angka) memetakan angka antara 0 dan 5039 ke permutasi unik, dan

f '(permutasi) memetakan permutasi kembali ke nomor asalnya.

Saya tidak peduli tentang korespondensi antara bilangan dan permutasi, asalkan setiap permutasi memiliki nomor uniknya sendiri.

Jadi, misalnya, saya mungkin memiliki fungsi di mana

f(0) = '1234567'
f'('1234567') = 0

Algoritme tercepat yang terlintas dalam pikiran adalah menghitung semua permutasi dan membuat tabel pencarian di kedua arah, sehingga, setelah tabel dibuat, f (0) akan menjadi O (1) dan f ('1234567') menjadi a mencari string. Namun, ini adalah memori haus, terutama ketika n menjadi besar.

Adakah yang bisa mengusulkan algoritma lain yang akan bekerja dengan cepat dan tanpa kerugian memori?

Untuk mendeskripsikan permutasi n elemen, Anda lihat bahwa untuk posisi akhir elemen pertama, Anda memiliki n kemungkinan, jadi Anda dapat mendeskripsikannya dengan angka antara 0 dan n-1. Untuk posisi akhir elemen berikutnya, Anda memiliki n-1 kemungkinan yang tersisa, sehingga Anda dapat mendeskripsikannya dengan angka antara 0 dan n-2.
Dan lain-lain sampai Anda memiliki n nomor.

Sebagai contoh untuk n = 5, perhatikan permutasi yang membawa abcdeke caebd.

• a, elemen pertama, berakhir di posisi kedua, jadi kami menetapkannya indeks 1 .
• bberakhir di posisi keempat, yang akan menjadi indeks 3, tetapi itu adalah posisi ketiga yang tersisa, jadi kami menetapkannya 2 .
• cberakhir di posisi tersisa pertama, yang selalu 0 .
• dberakhir di posisi terakhir yang tersisa, yang (dari hanya dua posisi tersisa) adalah 1 .
• eberakhir di satu-satunya posisi yang tersisa, diindeks pada 0 .

Jadi kami memiliki urutan indeks {1, 2, 0, 1, 0} .

Sekarang Anda tahu bahwa misalnya dalam bilangan biner, 'xyz' berarti z + 2y + 4x. Untuk bilangan desimal,
z + 10y + 100x. Setiap digit dikalikan dengan beberapa bobot, dan hasilnya dijumlahkan. Pola yang jelas dalam bobot adalah tentu saja bahwa bobotnya adalah w = b ^ k, dengan b basis bilangan dan k indeks digit. (Saya akan selalu menghitung digit dari kanan dan mulai dari indeks 0 untuk digit paling kanan. Begitu pula ketika saya berbicara tentang digit 'pertama' yang saya maksudkan paling kanan.)

The Alasan mengapa bobot untuk digit mengikuti pola ini adalah bahwa jumlah tertinggi yang dapat diwakili oleh angka dari 0 sampai k harus tepat 1 lebih rendah dari jumlah terendah yang dapat diwakili dengan hanya menggunakan digit k + 1. Dalam biner, 0111 harus lebih rendah dari 1000. Dalam desimal, 099999 harus lebih rendah dari 100000.

Pengkodean ke basis-variabel
Jarak antara angka-angka berikutnya menjadi tepat 1 adalah aturan penting. Menyadari hal ini, kita dapat merepresentasikan urutan indeks kita dengan nomor basis variabel . Basis untuk setiap digit adalah jumlah kemungkinan berbeda untuk digit tersebut. Untuk desimal, setiap digit memiliki 10 kemungkinan, untuk sistem kami digit paling kanan memiliki 1 kemungkinan dan digit paling kiri memiliki n kemungkinan. Tetapi karena digit paling kanan (angka terakhir dalam urutan kita) selalu 0, kita biarkan saja. Itu berarti kita memiliki basis 2 hingga n. Secara umum, digit ke-k akan memiliki basis b [k] = k + 2. Nilai tertinggi yang diperbolehkan untuk digit k adalah h [k] = b [k] - 1 = k + 1.

Aturan kita tentang bobot w [k] digit mensyaratkan bahwa jumlah dari h [i] * w [i], di mana i berpindah dari i = 0 ke i = k, sama dengan 1 * w [k + 1]. Dinyatakan berulang kali, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Bobot pertama w [0] harus selalu 1. Mulai dari sana, kami memiliki nilai berikut:

k    h[k] w[k]    

0    1    1  
1    2    2    
2    3    6    
3    4    24   
...  ...  ...
n-1  n    n!  

(Hubungan umum w [k-1] = k! Dengan mudah dibuktikan dengan induksi.)

Angka yang kita peroleh dari konversi urutan kita akan menjadi jumlah dari s [k] * w [k], dengan k berjalan dari 0 ke n-1. Di sini s [k] adalah elemen k'th (paling kanan, dimulai dari 0) dari barisan tersebut. Sebagai contoh, ambil {1, 2, 0, 1, 0} kami, dengan elemen paling kanan dilepas seperti yang disebutkan sebelumnya: {1, 2, 0, 1} . Jumlah kita adalah 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

Perhatikan bahwa jika kita mengambil posisi maksimum untuk setiap indeks, kita akan memiliki {4, 3, 2, 1, 0}, dan itu akan dikonversi menjadi 119. Karena bobot dalam penyandian angka kami dipilih sehingga kami tidak melewatkan nomor apa pun, semua angka 0 hingga 119 valid. Tepatnya ada 120 di antaranya, yaitu n! untuk n = 5 dalam contoh kita, tepatnya jumlah permutasi yang berbeda. Jadi Anda dapat melihat nomor yang dikodekan kami benar-benar menentukan semua kemungkinan permutasi.

Decoding dari variable-base
Decoding mirip dengan mengkonversi ke biner atau desimal. Algoritma yang umum adalah ini:

int number = 42;
int base = 2;
int[] bits = new int[n];

for (int k = 0; k < bits.Length; k++)
{
    bits[k] = number % base;
    number = number / base;
}

Untuk bilangan basis variabel kami:

int n = 5;
int number = 37;

int[] sequence = new int[n - 1];
int base = 2;

for (int k = 0; k < sequence.Length; k++)
{
    sequence[k] = number % base;
    number = number / base;

    base++; // b[k+1] = b[k] + 1
}

Ini dengan benar menerjemahkan 37 kembali ke {1, 2, 0, 1} ( sequenceakan ada {1, 0, 2, 1}dalam contoh kode ini, tapi terserah ... selama Anda mengindeks dengan tepat). Kita hanya perlu menambahkan 0 di ujung kanan (ingat elemen terakhir selalu hanya memiliki satu kemungkinan untuk posisi barunya) untuk mendapatkan kembali urutan awal kita {1, 2, 0, 1, 0}.

Mengizinkan daftar menggunakan urutan indeks
Anda dapat menggunakan algoritma di bawah ini untuk mengubah daftar menurut urutan indeks tertentu. Sayangnya, ini adalah algoritma O (n²).

int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];

for (int i = 0; i < n; i++)
{
    int s = sequence[i];
    int remainingPosition = 0;
    int index;

    // Find the s'th position in the permuted list that has not been set yet.
    for (index = 0; index < n; index++)
    {
        if (!set[index])
        {
            if (remainingPosition == s)
                break;

            remainingPosition++;
        }
    }

    permuted[index] = list[i];
    set[index] = true;
}

Representasi umum permutasi
Biasanya Anda tidak akan merepresentasikan permutasi secara tidak intuitif seperti yang kita lakukan, tetapi hanya dengan posisi absolut setiap elemen setelah permutasi diterapkan. Contoh kita {1, 2, 0, 1, 0} untuk abcdeto caebdbiasanya diwakili oleh {1, 3, 0, 4, 2}. Setiap indeks dari 0 hingga 4 (atau secara umum, 0 hingga n-1) muncul tepat sekali dalam representasi ini.

Menerapkan permutasi dalam formulir ini mudah:

int[] permutation = new int[] { 1, 3, 0, 4, 2 };

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

for (int i = 0; i < n; i++)
{
    permuted[permutation[i]] = list[i];
}

Membaliknya sangat mirip:

for (int i = 0; i < n; i++)
{
    list[i] = permuted[permutation[i]];
}

Mengonversi dari representasi kita ke representasi umum
Perhatikan bahwa jika kita menggunakan algoritme untuk mengubah daftar menggunakan urutan indeks kita, dan menerapkannya ke permutasi identitas {0, 1, 2, ..., n-1}, kita mendapatkan permutasi terbalik , direpresentasikan dalam bentuk umum. ( {2, 0, 4, 1, 3} dalam contoh kita).

Untuk mendapatkan premutasi non-terbalik, kami menerapkan algoritma permutasi yang baru saja saya tunjukkan:

int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];

for (int i = 0; i < n; i++)
{
    normal[identity[i]] = list[i];
}

Atau Anda bisa menerapkan permutasi secara langsung, dengan menggunakan algoritma permutasi terbalik:

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

int[] inverted = { 2, 0, 4, 1, 3 };

for (int i = 0; i < n; i++)
{
    permuted[i] = list[inverted[i]];
}

Perhatikan bahwa semua algoritme untuk menangani permutasi dalam bentuk umum adalah O (n), sedangkan menerapkan permutasi dalam bentuk kita adalah O (n²). Jika Anda perlu menerapkan permutasi beberapa kali, konversikan dulu ke representasi umum.

Saya menemukan algoritma O (n), berikut penjelasan singkatnya http://antoinecomeau.blogspot.ca/2014/07/mapping-between-permutations-and.html

public static int[] perm(int n, int k)
{
    int i, ind, m=k;
    int[] permuted = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) elems[i]=i;

    for(i=0;i<n;i++)
    {
            ind=m%(n-i);
            m=m/(n-i);
            permuted[i]=elems[ind];
            elems[ind]=elems[n-i-1];
    }

    return permuted;
}

public static int inv(int[] perm)
{
    int i, k=0, m=1;
    int n=perm.length;
    int[] pos = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) {pos[i]=i; elems[i]=i;}

    for(i=0;i<n-1;i++)
    {
            k+=m*pos[perm[i]];
            m=m*(n-i);
            pos[elems[n-i-1]]=pos[perm[i]];
            elems[pos[perm[i]]]=elems[n-i-1];
    }

    return k;
}

Kompleksitas dapat diturunkan ke n * log (n), lihat bagian 10.1.1 ("Kode Lehmer (tabel inversi)", hal.232ff) dari fxtbook: http://www.jjj.de/fxt/ #fxtbook lompat ke bagian 10.1.1.1 ("Komputasi dengan larik besar" hal.235) untuk metode cepat. Kode (GPLed, C ++) ada di halaman web yang sama.

Masalah terpecahkan. Namun, saya tidak yakin Anda masih membutuhkan solusinya setelah bertahun-tahun ini. LOL, saya baru bergabung dengan situs ini, jadi ... Periksa Kelas Permutasi Java saya. Anda dapat mendasarkan pada indeks untuk mendapatkan permutasi simbol, atau memberikan permutasi simbol lalu mendapatkan indeks.

Ini Kelas Premutasi saya

/**
 ****************************************************************************************************************
 * Copyright 2015 Fred Pang [email protected]
 ****************************************************************************************************************
 * A complete list of Permutation base on an index.
 * Algorithm is invented and implemented by Fred Pang [email protected]
 * Created by Fred Pang on 18/11/2015.
 ****************************************************************************************************************
 * LOL this is my first Java project. Therefore, my code is very much like C/C++. The coding itself is not
 * very professional. but...
 *
 * This Permutation Class can be use to generate a complete list of all different permutation of a set of symbols.
 * nPr will be n!/(n-r)!
 * the user can input       n = the number of items,
 *                          r = the number of slots for the items,
 *                          provided n >= r
 *                          and a string of single character symbols
 *
 * the program will generate all possible permutation for the condition.
 *
 * Say if n = 5, r = 3, and the string is "12345", it will generate sll 60 different permutation of the set
 * of 3 character strings.
 *
 * The algorithm I used is base on a bin slot.
 * Just like a human or simply myself to generate a permutation.
 *
 * if there are 5 symbols to chose from, I'll have 5 bin slot to indicate which symbol is taken.
 *
 * Note that, once the Permutation object is initialized, or after the constructor is called, the permutation
 * table and all entries are defined, including an index.
 *
 * eg. if pass in value is 5 chose 3, and say the symbol string is "12345"
 * then all permutation table is logically defined (not physically to save memory).
 * It will be a table as follows
 *  index  output
 *      0   123
 *      1   124
 *      2   125
 *      3   132
 *      4   134
 *      5   135
 *      6   143
 *      7   145
 *      :     :
 *      58  542
 *      59  543
 *
 * all you need to do is call the "String PermGetString(int iIndex)" or the "int[] PermGetIntArray(int iIndex)"
 * function or method with an increasing iIndex, starting from 0 to getiMaxIndex() - 1. It will return the string
 * or the integer array corresponding to the index.
 *
 * Also notice that in the input string is "12345" of  position 01234, and the output is always in accenting order
 * this is how the permutation is generated.
 *
 * ***************************************************************************************************************
 * ====  W a r n i n g  ====
 * ***************************************************************************************************************
 *
 * There is very limited error checking in this class
 *
 * Especially the  int PermGetIndex(int[] iInputArray)  method
 * if the input integer array contains invalid index, it WILL crash the system
 *
 * the other is the string of symbol pass in when the object is created, not sure what will happen if the
 * string is invalid.
 * ***************************************************************************************************************
 *
 */
public class Permutation
{
    private boolean bGoodToGo = false;      // object status
    private boolean bNoSymbol = true;
    private BinSlot slot;                   // a bin slot of size n (input)
    private int nTotal;                     // n number for permutation
    private int rChose;                     // r position to chose
    private String sSymbol;                 // character string for symbol of each choice
    private String sOutStr;
    private int iMaxIndex;                  // maximum index allowed in the Get index function
    private int[] iOutPosition;             // output array
    private int[] iDivisorArray;            // array to do calculation

    public Permutation(int inCount, int irCount, String symbol)
    {
        if (inCount >= irCount)
        {
            // save all input values passed in
            this.nTotal = inCount;
            this.rChose = irCount;
            this.sSymbol = symbol;

            // some error checking
            if (inCount < irCount || irCount <= 0)
                return;                                 // do nothing will not set the bGoodToGo flag

            if (this.sSymbol.length() >= inCount)
            {
                bNoSymbol = false;
            }

            // allocate output storage
            this.iOutPosition = new int[this.rChose];

            // initialize the bin slot with the right size
            this.slot = new BinSlot(this.nTotal);

            // allocate and initialize divid array
            this.iDivisorArray = new int[this.rChose];

            // calculate default values base on n & r
            this.iMaxIndex = CalPremFormula(this.nTotal, this.rChose);

            int i;
            int j = this.nTotal - 1;
            int k = this.rChose - 1;

            for (i = 0; i < this.rChose; i++)
            {
                this.iDivisorArray[i] = CalPremFormula(j--, k--);
            }
            bGoodToGo = true;       // we are ready to go
        }
    }

    public String PermGetString(int iIndex)
    {
        if (!this.bGoodToGo) return "Error: Object not initialized Correctly";
        if (this.bNoSymbol) return "Error: Invalid symbol string";
        if (!this.PermEvaluate(iIndex)) return "Invalid Index";

        sOutStr = "";
        // convert string back to String output
        for (int i = 0; i < this.rChose; i++)
        {
            String sTempStr = this.sSymbol.substring(this.iOutPosition[i], iOutPosition[i] + 1);
            this.sOutStr = this.sOutStr.concat(sTempStr);
        }
        return this.sOutStr;
    }

    public int[] PermGetIntArray(int iIndex)
    {
        if (!this.bGoodToGo) return null;
        if (!this.PermEvaluate(iIndex)) return null ;
        return this.iOutPosition;
    }

    // given an int array, and get the index back.
    //
    //  ====== W A R N I N G ======
    //
    // there is no error check in the array that pass in
    // if any invalid value in the input array, it can cause system crash or other unexpected result
    //
    // function pass in an int array generated by the PermGetIntArray() method
    // then return the index value.
    //
    // this is the reverse of the PermGetIntArray()
    //
    public int PermGetIndex(int[] iInputArray)
    {
        if (!this.bGoodToGo) return -1;
        return PermDoReverse(iInputArray);
    }


    public int getiMaxIndex() {
    return iMaxIndex;
}

    // function to evaluate nPr = n!/(n-r)!
    public int CalPremFormula(int n, int r)
    {
        int j = n;
        int k = 1;
        for (int i = 0; i < r; i++, j--)
        {
            k *= j;
        }
        return k;
    }


//  PermEvaluate function (method) base on an index input, evaluate the correspond permuted symbol location
//  then output it to the iOutPosition array.
//
//  In the iOutPosition[], each array element corresponding to the symbol location in the input string symbol.
//  from location 0 to length of string - 1.

    private boolean PermEvaluate(int iIndex)
    {
        int iCurrentIndex;
        int iCurrentRemainder;
        int iCurrentValue = iIndex;
        int iCurrentOutSlot;
        int iLoopCount;

        if (iIndex >= iMaxIndex)
            return false;

        this.slot.binReset();               // clear bin content
        iLoopCount = 0;
        do {
            // evaluate the table position
            iCurrentIndex = iCurrentValue / this.iDivisorArray[iLoopCount];
            iCurrentRemainder = iCurrentValue % this.iDivisorArray[iLoopCount];

            iCurrentOutSlot = this.slot.FindFreeBin(iCurrentIndex);     // find an available slot
            if (iCurrentOutSlot >= 0)
                this.iOutPosition[iLoopCount] = iCurrentOutSlot;
            else return false;                                          // fail to find a slot, quit now

            this.slot.setStatus(iCurrentOutSlot);                       // set the slot to be taken
            iCurrentValue = iCurrentRemainder;                          // set new value for current value.
            iLoopCount++;                                               // increase counter
        } while (iLoopCount < this.rChose);

        // the output is ready in iOutPosition[]
        return true;
    }

    //
    // this function is doing the reverse of the permutation
    // the input is a permutation and will find the correspond index value for that entry
    // which is doing the opposit of the PermEvaluate() method
    //
    private int PermDoReverse(int[] iInputArray)
    {
        int iReturnValue = 0;
        int iLoopIndex;
        int iCurrentValue;
        int iBinLocation;

        this.slot.binReset();               // clear bin content

        for (iLoopIndex = 0; iLoopIndex < this.rChose; iLoopIndex++)
        {
            iCurrentValue = iInputArray[iLoopIndex];
            iBinLocation = this.slot.BinCountFree(iCurrentValue);
            this.slot.setStatus(iCurrentValue);                          // set the slot to be taken
            iReturnValue = iReturnValue + iBinLocation * this.iDivisorArray[iLoopIndex];
        }
        return iReturnValue;
    }


    /*******************************************************************************************************************
     *******************************************************************************************************************
     * Created by Fred on 18/11/2015.   [email protected]
     *
     * *****************************************************************************************************************
     */
    private static class BinSlot
    {
        private int iBinSize;       // size of array
        private short[] eStatus;    // the status array must have length iBinSize

        private BinSlot(int iBinSize)
        {
            this.iBinSize = iBinSize;               // save bin size
            this.eStatus = new short[iBinSize];     // llocate status array
        }

        // reset the bin content. no symbol is in use
        private void binReset()
        {
            // reset the bin's content
            for (int i = 0; i < this.iBinSize; i++) this.eStatus[i] = 0;
        }

        // set the bin position as taken or the number is already used, cannot be use again.
        private void  setStatus(int iIndex) { this.eStatus[iIndex]= 1; }

        //
        // to search for the iIndex th unused symbol
        // this is important to search through the iindex th symbol
        // because this is how the table is setup. (or the remainder means)
        // note: iIndex is the remainder of the calculation
        //
        // for example:
        // in a 5 choose 3 permutation symbols "12345",
        // the index 7 item (count starting from 0) element is "1 4 3"
        // then comes the index 8, 8/12 result 0 -> 0th symbol in symbol string = '1'
        // remainder 8. then 8/3 = 2, now we need to scan the Bin and skip 2 unused bins
        //              current the bin looks 0 1 2 3 4
        //                                    x o o o o     x -> in use; o -> free only 0 is being used
        //                                      s s ^       skipped 2 bins (bin 1 and 2), we get to bin 3
        //                                                  and bin 3 is the bin needed. Thus symbol "4" is pick
        // in 8/3, there is a remainder 2 comes in this function as 2/1 = 2, now we have to pick the empty slot
        // for the new 2.
        // the bin now looks 0 1 2 3 4
        //                   x 0 0 x 0      as bin 3 was used by the last value
        //                     s s   ^      we skip 2 free bins and the next free bin is bin 4
        //                                  therefor the symbol "5" at the symbol array is pick.
        //
        // Thus, for index 8  "1 4 5" is the symbols.
        //
        //
        private int FindFreeBin(int iIndex)
        {
            int j = iIndex;

            if (j < 0 || j > this.iBinSize) return -1;               // invalid index

            for (int i = 0; i < this.iBinSize; i++)
            {
                if (this.eStatus[i] == 0)       // is it used
                {
                    // found an empty slot
                    if (j == 0)                 // this is a free one we want?
                        return i;               // yes, found and return it.
                    else                        // we have to skip this one
                        j--;                    // else, keep looking and count the skipped one
                }
            }
            assert(true);           // something is wrong
            return -1;              // fail to find the bin we wanted
        }

        //
        // this function is to help the PermDoReverse() to find out what is the corresponding
        // value during should be added to the index value.
        //
        // it is doing the opposite of int FindFreeBin(int iIndex) method. You need to know how this
        // FindFreeBin() works before looking into this function.
        //
        private int BinCountFree(int iIndex)
        {
            int iRetVal = 0;
            for (int i = iIndex; i > 0; i--)
            {
                if (this.eStatus[i-1] == 0)       // it is free
                {
                    iRetVal++;
                }
            }
            return iRetVal;
        }
    }
}
// End of file - Permutation.java

dan inilah Kelas Utama saya untuk menunjukkan cara menggunakan kelas.

/*
 * copyright 2015 Fred Pang
 *
 * This is the main test program for testing the Permutation Class I created.
 * It can be use to demonstrate how to use the Permutation Class and its methods to generate a complete
 * list of a permutation. It also support function to get back the index value as pass in a permutation.
 *
 * As you can see my Java is not very good. :)
 * This is my 1st Java project I created. As I am a C/C++ programmer for years.
 *
 * I still have problem with the Scanner class and the System class.
 * Note that there is only very limited error checking
 *
 *
 */

import java.util.Scanner;

public class Main
{
    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args)
    {
        Permutation perm;       // declear the object
        String sOutString = "";
        int nCount;
        int rCount;
        int iMaxIndex;

        // Get user input
        System.out.println("Enter n: ");
        nCount = scanner.nextInt();

        System.out.println("Enter r: ");
        rCount = scanner.nextInt();

        System.out.println("Enter Symbol: ");
        sOutString = scanner.next();

        if (sOutString.length() < rCount)
        {
            System.out.println("String too short, default to numbers");
            sOutString = "";
        }

        // create object with user requirement
        perm = new Permutation(nCount, rCount, sOutString);

        // and print the maximum count
        iMaxIndex = perm.getiMaxIndex();
        System.out.println("Max count is:" + iMaxIndex);

        if (!sOutString.isEmpty())
        {
            for (int i = 0; i < iMaxIndex; i++)
            {   // print out the return permutation symbol string
                System.out.println(i + " " + perm.PermGetString(i));
            }
        }
        else
        {
            for (int i = 0; i < iMaxIndex; i++)
            {
                System.out.print(i + " ->");

                // Get the permutation array
                int[] iTemp = perm.PermGetIntArray(i);

                // print out the permutation
                for (int j = 0; j < rCount; j++)
                {
                    System.out.print(' ');
                    System.out.print(iTemp[j]);
                }

                // to verify my PermGetIndex() works. :)
                if (perm.PermGetIndex(iTemp)== i)
                {
                    System.out.println(" .");
                }
                else
                {   // oops something is wrong :(
                    System.out.println(" ***************** F A I L E D *************************");
                    assert(true);
                    break;
                }
            }
        }
    }
}
//
// End of file - Main.java

Selamat bersenang-senang. :)

Setiap elemen dapat berada di salah satu dari tujuh posisi. Untuk mendeskripsikan posisi satu elemen, Anda membutuhkan tiga bit. Itu berarti Anda dapat menyimpan posisi semua elemen dalam nilai 32bit. Itu jauh dari efisien, karena representasi ini bahkan akan memungkinkan semua elemen berada pada posisi yang sama, tetapi saya percaya bit-masking seharusnya cukup cepat.

Namun, dengan lebih dari 8 posisi, Anda memerlukan sesuatu yang lebih bagus.

Ini kebetulan menjadi fungsi bawaan di J :

   A. 1 2 3 4 5 6 7
0
   0 A. 1 2 3 4 5 6 7
1 2 3 4 5 6 7

   ?!7
5011
   5011 A. 1 2 3 4 5 6 7
7 6 4 5 1 3 2
   A. 7 6 4 5 1 3 2
5011

Anda dapat mengenkode permutasi menggunakan algoritme rekursif. Jika permutasi-N (beberapa urutan angka {0, .., N-1}) berbentuk {x, ...} maka enkodekan sebagai x + N * pengkodean (N-1) -permutasi diwakili oleh "..." pada angka {0, N-1} - {x}. Kedengarannya seperti suap, berikut beberapa kodenya:

// perm[0]..perm[n-1] must contain the numbers in {0,..,n-1} in any order.
int permToNumber(int *perm, int n) {
  // base case
  if (n == 1) return 0;

  // fix up perm[1]..perm[n-1] to be a permutation on {0,..,n-2}.
  for (int i = 1; i < n; i++) {
    if (perm[i] > perm[0]) perm[i]--;
  }

  // recursively compute
  return perm[0] + n * permToNumber(perm + 1, n - 1);
}

// number must be >=0, < n!
void numberToPerm(int number, int *perm, int n) {
  if (n == 1) {
    perm[0] = 0;
    return;
  }
  perm[0] = number % n;
  numberToPerm(number / n, perm + 1, n - 1);

  // fix up perm[1] .. perm[n-1]
  for (int i = 1; i < n; i++) {
    if (perm[i] >= perm[0]) perm[i]++;
  }
}

Algoritma ini adalah O (n ^ 2). Poin bonus jika ada yang memiliki algoritma O (n).

Sungguh pertanyaan yang menarik!

Jika semua elemen Anda adalah angka, Anda mungkin ingin mempertimbangkan untuk mengubahnya dari string menjadi angka sebenarnya. Kemudian Anda akan dapat mengurutkan semua permutasi dengan menyusunnya, dan menempatkannya dalam sebuah array. Setelah itu, Anda akan terbuka untuk salah satu dari berbagai algoritma pencarian di luar sana.

Saya terburu-buru dalam jawaban saya sebelumnya (dihapus), saya memiliki jawaban yang sebenarnya. Ini disediakan oleh konsep serupa, faktoradic , dan terkait dengan permutasi (jawaban saya terkait dengan kombinasi, saya minta maaf atas kebingungan itu). Saya benci hanya memposting tautan wikipedia, tetapi saya menulis artikel yang saya lakukan beberapa waktu yang lalu tidak dapat dipahami karena beberapa alasan. Jadi, saya dapat mengembangkannya nanti jika diminta.

Ada sebuah buku yang menulis tentang ini. Maaf, tapi saya tidak ingat namanya (kemungkinan besar Anda akan menemukannya dari wikipedia). tapi bagaimanapun saya menulis implementasi python dari sistem pencacahan itu: http://kks.cabal.fi/Kombinaattori Beberapa di antaranya dalam bahasa Finlandia, tetapi cukup salin kode dan variabel nama ...

Saya memiliki pertanyaan yang tepat ini dan berpikir saya akan memberikan solusi Python saya. Ini O (n ^ 2).

import copy

def permute(string, num):
    ''' generates a permutation '''
    def build_s(factoradic): # Build string from factoradic in list form
        string0 = copy.copy(string)
        n = []
        for i in range(len(factoradic)):
            n.append(string0[factoradic[i]])
            del string0[factoradic[i]]
        return n

    f = len(string)
    factoradic = []
    while(f != 0): # Generate factoradic number list
        factoradic.append(num % f)
        num = (num - factoradic[-1])//f
        f -= 1

    return build_s(factoradic)

s = set()
# Print 120 permutations of this string
for i in range(120):
    m = permute(list('abcde'), i)
    s.add(''.join(m))

print(len(s)) # Check that we have 120 unique permutations

Ini sangat mudah; setelah membuat representasi faktorad dari nomor tersebut, saya hanya memilih dan menghapus karakter dari string. Menghapus dari string adalah mengapa ini adalah solusi O (n ^ 2).

Solusi Antoine lebih baik untuk performa.

Sebuah pertanyaan terkait adalah menghitung permutasi terbalik, permutasi yang akan mengembalikan vektor yang diijinkan ke urutan semula ketika hanya array permutasi yang diketahui. Berikut adalah kode O (n) (dalam PHP):

// Compute the inverse of a permutation
function GetInvPerm($Perm)
    {
    $n=count($Perm);
    $InvPerm=[];
    for ($i=0; $i<$n; ++$i)
        $InvPerm[$Perm[$i]]=$i;
    return $InvPerm;
    } // GetInvPerm

Perangkat Lunak David Spector Springtime