Быстрая перестановка -> число -> алгоритмы отображения перестановок
https://stackoverflow.com/questions/1506078
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть n элементов.Для примера, допустим, 7 элементов, 1234567.Я знаю, что их 7!= 5040 возможных перестановок из этих 7 элементов.
Мне нужен быстрый алгоритм, состоящий из двух функций:
f(число) преобразует число от 0 до 5039 в уникальную перестановку, и
f'(перестановка) возвращает перестановку обратно к числу, из которого она была сгенерирована.
Меня не волнует соответствие между числом и перестановкой, при условии, что каждая перестановка имеет свой собственный уникальный номер.
Так, например, у меня могли бы быть функции, где
f(0) = '1234567'
f'('1234567') = 0
Самый быстрый алгоритм, который приходит на ум, - это перечислить все перестановки и создать таблицу поиска в обоих направлениях, чтобы после создания таблиц f (0) было O (1), а f('1234567') было поиском по строке.Однако это приводит к нехватке памяти, особенно когда n становится большим.
Может ли кто-нибудь предложить другой алгоритм, который работал бы быстро и без недостатка памяти?
Решение
Чтобы описать перестановку из n элементов, вы видите, что для позиции, в которой заканчивается первый элемент, у вас есть n возможностей, поэтому вы можете описать это числом от 0 до n-1.Для позиции, в которой заканчивается следующий элемент, у вас есть n-1 оставшихся возможностей, поэтому вы можете описать это числом от 0 до n-2.
И так далее, пока у вас не будет n чисел.
В качестве примера для n = 5 рассмотрим перестановку, которая приводит abcde Для caebd.
a, первый элемент, заканчивается на второй позиции, поэтому мы присваиваем ему индекс 1.bзаканчивается на четвертой позиции, которая будет иметь индекс 3, но это третья оставшаяся позиция, поэтому мы присваиваем ей 2.cзаканчивается на первой оставшейся позиции, которая всегда 0.dзаканчивается на последней оставшейся позиции, которая (из всего лишь двух оставшихся позиций) является 1.eзаканчивается в единственной оставшейся позиции, индексируемой по 0.
Итак, у нас есть последовательность индексов {1, 2, 0, 1, 0}.
Теперь вы знаете, что, например, в двоичном числе 'xyz' означает z + 2y + 4x.Для десятичного числа,
это z + 10y + 100x.Каждая цифра умножается на некоторый вес, и результаты суммируются.Очевидная закономерность в весе, конечно, заключается в том, что вес равен w = b ^ k, где b - основание числа, а k - индекс цифры.(Я всегда буду считать цифры справа и начинать с индекса 0 для самой правой цифры.Точно так же, когда я говорю о "первой" цифре, я имею в виду самую правую.)
В Причина причина, по которой веса для цифр следуют этому шаблону, заключается в том, что наибольшее число, которое может быть представлено цифрами от 0 до k, должно быть ровно на 1 меньше наименьшего числа, которое может быть представлено только с помощью цифры k + 1.В двоичном формате значение 0111 должно быть на единицу меньше 1000.В десятичной системе счисления 099999 должно быть на единицу меньше 100000.
Кодирование в переменную-база
Важным правилом является интервал между последующими числами, равный ровно 1.Понимая это, мы можем представить нашу последовательность индексов с помощью переменная-базовое число.Базой для каждой цифры является количество различных возможностей для этой цифры.Для десятичной системы каждая цифра имеет 10 возможностей, для нашей системы крайняя правая цифра будет иметь 1 возможность, а крайняя левая будет иметь n возможностей.Но поскольку крайняя правая цифра (последнее число в нашей последовательности) всегда равна 0, мы ее опускаем.Это означает, что у нас остаются основания от 2 до n.В общем случае k-я цифра будет иметь основание b[k] = k + 2.Максимально допустимое значение для цифры k равно h [k] = b [k] - 1 = k + 1.
Наше правило о весах w[k] цифр требует, чтобы сумма h [i] * w [i], где i переходит от i = 0 к i = k, была равна 1 * w[k+1].Повторяю, w [k + 1] = w [k] + h [k] * w [k] = w [k]* (h [k] + 1).Первый вес w[0] всегда должен быть равен 1.Начиная с этого момента, мы имеем следующие значения:
k h[k] w[k]
0 1 1
1 2 2
2 3 6
3 4 24
... ... ...
n-1 n n!
(Общее соотношение w[k-1] = k!легко доказывается индукцией.)
Число, которое мы получим в результате преобразования нашей последовательности, будет тогда суммой s[k] * w [k], причем k изменяется от 0 до n-1.Здесь s[k] - это k-й (самый правый, начинающийся с 0) элемент последовательности.В качестве примера возьмем наш {1, 2, 0, 1, 0}, с удаленным крайним правым элементом, как упоминалось ранее: {1, 2, 0, 1}.Наша сумма равна 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37.
Обратите внимание, что если мы возьмем максимальную позицию для каждого индекса, то получим {4, 3, 2, 1, 0}, и это преобразуется в 119.Поскольку веса в нашей кодировке чисел были выбраны таким образом, чтобы мы не пропускали никаких чисел, все числа от 0 до 119 являются допустимыми.Их ровно 120, то есть n!для n = 5 в нашем примере - точное количество различных перестановок.Таким образом, вы можете видеть, что наши закодированные числа полностью определяют все возможные перестановки.
Декодирование с переменной базы
Декодирование аналогично преобразованию в двоичную или десятичную систему счисления.Общий алгоритм таков:
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;
}
Для нашей переменной-базовый номер:
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
}
Это правильно расшифровывает наш 37 обратно в {1, 2, 0, 1} (sequence было бы {1, 0, 2, 1} в этом примере кода, но неважно ...до тех пор, пока вы индексируете соответствующим образом).Нам просто нужно добавить 0 в правом конце (помните, что у последнего элемента всегда есть только одна возможность для его новой позиции), чтобы вернуть нашу исходную последовательность {1, 2, 0, 1, 0}.
Перестановка списка с использованием последовательности индексов
Вы можете использовать приведенный ниже алгоритм для перестановки списка в соответствии с определенной последовательностью индексов.К сожалению, это алгоритм O (n2).
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;
}
Общее представление перестановок
Обычно вы представляли бы перестановку не так неинтуитивно, как это сделали мы, а просто по абсолютному положению каждого элемента после применения перестановки.Наш пример {1, 2, 0, 1, 0} для abcde Для caebd обычно представлен {1, 3, 0, 4, 2}.Каждый индекс от 0 до 4 (или, в общем случае, от 0 до n-1) встречается в этом представлении ровно один раз.
Применить перестановку в этой форме несложно:
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];
}
Переворачивание это очень похоже:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
Преобразование из нашего представления в общее представление
Обратите внимание, что если мы воспользуемся нашим алгоритмом для перестановки списка, используя нашу последовательность индексов, и применим его к перестановке идентификаторов {0, 1, 2, ..., n-1}, мы получим обратный перестановка, представленная в общей форме.({2, 0, 4, 1, 3} в нашем примере).
Чтобы получить неинвертированную предварительную мутацию, мы применяем алгоритм перестановки, который я только что показал:
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];
}
Или вы можете просто применить перестановку напрямую, используя алгоритм обратной перестановки:
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]];
}
Обратите внимание, что все алгоритмы для работы с перестановками в общей форме - O (n), в то время как применение перестановки в нашей форме - O(n2).Если вам нужно применить перестановку несколько раз, сначала преобразуйте ее в общее представление.
Другие советы
Я нашел алгоритм O (n), вот краткое объяснение 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;
}
Сложность может быть уменьшена до n * log (n), см. Раздел 10.1.1 ("Код Лемера (таблица инверсий)", стр.232ff) fxtbook: http://www.jjj.de/fxt/#fxtbook перейдите к разделу 10.1.1.1 ("Вычисления с большими массивами", стр.235) для быстрого метода.Код (GPLed, C ++) находится на той же веб-странице.
Каждый элемент может находиться в одном из семи положений.Чтобы описать положение одного элемента, вам понадобилось бы три бита.Это означает, что вы можете сохранить положение всех элементов в 32-битном значении.Это далеко не эффективно, поскольку такое представление даже позволило бы всем элементам находиться в одном и том же положении, но я считаю, что битовая маскировка должна быть достаточно быстрой.
Однако с более чем 8 позициями вам понадобится что-то более изящное.
Оказывается, это встроенная функция в 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
Проблема решена.Однако я не уверен, что по прошествии этих лет вам все еще нужно это решение.ЛОЛ, я только что присоединился к этому сайту, так что ...Проверьте мой класс Java Permutation.Вы можете основываться на индексе, чтобы получить перестановку символов, или задать перестановку символов, а затем получить индекс.
Вот мой Предварительный класс
/**
****************************************************************************************************************
* Copyright 2015 Fred Pang fred@pnode.com
****************************************************************************************************************
* A complete list of Permutation base on an index.
* Algorithm is invented and implemented by Fred Pang fred@pnode.com
* 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. fred@pnode.com
*
* *****************************************************************************************************************
*/
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
и вот мой Основной класс для демонстрации того, как использовать этот класс.
/*
* 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
Получайте удовольствие.:)
Вы можете кодировать перестановки с помощью рекурсивного алгоритма.Если N-перестановка (некоторый порядок чисел {0,..,N-1}) имеет вид {x, ...}, то закодируйте ее как x + N * кодировку (N-1)-перестановки, представленную "..." для чисел {0, N-1} - {x}.Звучит как набитый рот, вот немного кода:
// 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]++;
}
}
Этот алгоритм равен O(n^2).Бонусные баллы, если у кого-нибудь есть алгоритм O (n).
Какой интересный вопрос!
Если все ваши элементы являются числами, вы можете рассмотреть возможность преобразования их из строк в реальные числа.Тогда вы смогли бы отсортировать все перестановки, расположив их по порядку, и поместить их в массив.После этого вы были бы открыты для любого из существующих различных алгоритмов поиска.
Я был поспешен в своем предыдущем ответе (удален), однако у меня есть реальный ответ.Это обеспечивается аналогичной концепцией, факторидический, и связан с перестановками (мой ответ связан с комбинациями, я приношу извинения за эту путаницу).Я ненавижу просто публиковать ссылки на википедию, но то, что я написал некоторое время назад, по какой-то причине неразборчиво.Итак, я могу подробнее остановиться на этом позже, если потребуется.
Об этом написана книга.Извините, но я не помню его названия (вполне вероятно, вы найдете его в Википедии).но в любом случае я написал реализацию этой системы перечисления на python: http://kks.cabal.fi/Kombinaattori Часть из них на финском, но просто скопируйте код и назовите переменные ...
Связанный с этим вопрос заключается в вычислении обратной перестановки, перестановки, которая восстановит переставленные векторы в исходном порядке, когда известен только массив перестановок.Вот код O (n) (на 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
Дэвид Спектор Весеннее программное обеспечение
У меня был именно этот вопрос, и я подумал, что предоставлю свое решение на Python.Это 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
Это довольно прямолинейно;после генерации факторизованного представления числа я просто выбираю и удаляю символы из строки.Удаление из строки - вот почему это решение типа O (n ^ 2).
Решение Антуана лучше по производительности.
