以唯一给定索引在O(n)内获取排列
我想要一个叫做 get_permutation 的函数，它接收一个列表 l 和一个索引 i，返回一个 l 的排列。这个排列要确保对于所有大于 0 且小于 n! 的 i，排列都是唯一的（这里 n = len(l)）。
也就是说，如果 i 和 j 不相等（i!=j），那么 get_permutation(l,i) 和 get_permutation(l,j) 的结果也应该不一样，前提是 0 <= i 和 j < len(l)!。
此外，这个函数的运行时间要在 O(n) 的范围内。
举个例子，如果这个函数不涉及指数级的复杂度，它就能满足这些要求：
def get_permutation(l, i):
return list(itertools.permutations(l))[i]
有没有人能提供一个解决上述问题的方法？
编辑：我想要的是从索引获取排列，而不是从排列获取索引。
5 个回答
有点晚了……下面是C#代码，应该能给你想要的结果：
using System;
using System.Collections.Generic;
namespace WpfPermutations
{
public class PermutationOuelletLexico3<T>
{
// ************************************************************************
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; }
// ************************************************************************
/// <summary>
/// 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.
/// </summary>
/// <param name="sortIndex"></param>
/// <param name="result">Value is not used as inpu, only as output. Re-use buffer in order to save memory</param>
/// <returns></returns>
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;
}
}
// ************************************************************************
/// <summary>
/// Calc the index, relative to _sortedValues, of the permutation received
/// as argument. Returned index is 0 based.
/// </summary>
/// <param name="values"></param>
/// <returns></returns>
public long GetIndexOfValues(T[] values)
{
int size = _sortedValues.Length;
long valuesIndex = 0;
List<T> valuesLeft = new List<T>(_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;
}
// ************************************************************************
}
}
更新：可能是重复的问题，详情请见如何找到第n个排列而不计算其他排列，那里面有算法。
如果len(l)的值比较小，你可以提前计算出perm_index = permutations(range(len(l)))，然后把它当作一个包含索引的列表，方便你访问实际的数据。
此外，如果你已经有了一个从range(len(l))生成的排列列表，而你需要的是range(len(l) - 1)的排列，你可以这样做：
[x - 1 for x in perm_index[i][1:]]
这个方法利用了生成的排列是按顺序排列的这个特点。
根据这个链接 http://www.2ality.com/2013/03/permutations.html，这里有一个可能的解决方案。正如@Gassa提到的，elements.pop这个操作不是恒定的，所以这个解决方案在列表长度上不是线性的。因此，我不会把这个标记为被接受的答案。不过，它确实能完成任务。
def integerToCode(idx, permSize):
if (permSize <= 1):
return [0]
multiplier = math.factorial(permSize-1)
digit =idx / multiplier
return [digit] + integerToCode(idx % multiplier, permSize-1)
def codeToPermutation(elements, code):
return map(lambda i: elements.pop(i), code)
def get_permutation(l, i):
c = integerToCode(i, len(l))
return codeToPermutation(list(l), c)
这个解决方案的运行速度是 O(1)（也就是查找字典的平均成本）:
代码
#!/usr/bin/env python
import itertools
def get_permutation():
memoize = {}
def _memoizer(l, i):
if str(l) in memoize and i not in memoize[str(l)]:
memoize[str(l)][i] = memoize[str(l)]['permutations'].next()
else:
p = itertools.permutations(l)
memoize[str(l)] = {'permutations': p}
memoize[str(l)][i] = memoize[str(l)]['permutations'].next()
return memoize[str(l)][i]
return _memoizer
if __name__ == '__main__':
get_permutation = get_permutation()
l1 = list(range(10))
l2 = list(range(5))
print(get_permutation(l1, 1))
print(get_permutation(l1, 20))
print(get_permutation(l2, 3))
输出
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
(0, 1, 2, 3, 4, 5, 6, 7, 9, 8)
(0, 1, 2, 3, 4)
原理
这段代码把所有之前的调用都存储在一个字典里。同时，它也保存了排列对象。所以如果有新的排列请求，就会使用下一个排列。
这段代码使用了 itertools.permutations 这个库。
如果你不在乎每个排列对应哪个索引，那么有一种O(n)的解决方案是可能的，前提是我们认为用任意整数进行的算术运算是O(1)的。
比如，可以参考Wendy Myrvold和Frank Ruskey的论文“线性时间内排列的排名和反排名”。
简单来说，这里有两个主要的思路。
(1) 考虑使用Fisher-Yates洗牌方法来生成一个随机排列（下面是伪代码）：
p = [0, 1, ..., n-1]
for i := 0 upto n-1:
j := random_integer (0, i)
exchange p[i] and p[j]
这个转换是单射的：如果我们给它一个不同的随机整数序列，它一定会生成一个不同的排列。所以，我们可以把随机整数换成非随机的：第一个是0，第二个是0或1，……最后一个可以是从0到n-1的任何整数。
(2) 对于n个元素，有n!种排列。我们现在想做的是把一个从0到n!-1的整数写成阶乘数系统：最后一位总是0，前一位是0或1，……第一位有n种可能，从0到n-1。因此，我们会得到一个唯一的序列来输入到上面的伪代码中。
现在，如果我们把这个数字除以1到n之间的整数视为O(1)的操作，那么将数字转换为阶乘系统需要O(n)次这样的除法。严格来说，这并不完全正确：对于较大的n，数字n!大约包含O(n log n)个二进制位，而除法的成本与位数有关。
实际上，对于小的n，O(n^2)或O(n log n)的方法来排名或反排名一个排列，以及需要O(2^n)或O(n!)内存来存储一些预计算值的方法，可能比涉及整数除法的O(n)方法更快，因为在现代处理器上，整数除法相对较慢。对于足够大的n，以至于n!无法放入一个机器字中，“如果阶乘级整数运算是O(1)的，那么就是O(n)”的论点就不成立了。因此，对于小n和大n来说，如果你不坚持理论上是O(n)，可能会更好一些。