找到没有元素保留的排列

Question

我正在处理每个元素与其原始位置不同的排列。我想要一个给出{输入长度，行和数字}的算法，它会给我输出数字。这是一个例子：

如果输入长度为4，那么0123的所有排列都是：

0123,0132,0213,0231,0312,0321,
1023,1032,1203,1230,1302,1320,
2013,2031,2103,2130,2301,2310,
3012,3021,3102,3120,3201,3210

没有数字位于同一位置的排列（每个数字已经移动）：

1032,1230,1302,
2031,2301,2310,
3012,3201,3210

编号从0开始，因此如果函数的输入是{4,0,0}，则输出应该是第0（第一）排列的第0（最左边）数字。 1032的第一个数字是1.

如果输入为{4,1,1}，则输出为1230的第二个数字，即2。

行数可能更大于排列的nubmer。在这种情况下，取余数作为排列数的模数（在上面的例子中，行模9）。

用c语言会很棒。

（这不是功课，而是工作。如果你必须知道的话，Cuckoo哈希。我想随机选择我将在每个阶段进行的交换，以确定当表的数量是多少时它是否优于BFS大于两个。）

Answer 1

Python中的暴力方法（您可以使用它来测试您的C实现）：

#!/usr/bin/env python
from itertools import ifilter, islice, permutations

def f(length, row, digit):
    """
    >>> f(4, 0, 0)
    1
    >>> f(4, 1, 1)
    2
    """
    # 1. enumerate all permutations of range (range(3) -> [0,1,2], ..)
    # 2. filter out permutations that have digits inplace
    # 3. get n-th permutation (n -> row)
    # 4. get n-th digit of the permutation (n -> digit)
    return nth(ifilter(not_inplace, permutations(range(length))), row)[digit]

def not_inplace(indexes):
    """Return True if all indexes are not on their places.

    """
    return all(i != d for i, d in enumerate(indexes))

def nth(iterable, n, default=None):
    """Return the nth item or a default value.

    http://docs.python.org/library/itertools.html#recipes
    """
    return next(islice(iterable, n, None), default)

if __name__=="__main__":
    import doctest; doctest.testmod()

Answer 2

为什么不只是构建一个树并迭代它？

例如，如果你有数字 0123 ，那么你知道最左边的数字只能来自 set {1,2,3} 。这将成为您树中的第一级。

然后，如果沿着从1开始的路径，您只有三个选项， {0,2,3} 。如果你沿着第一级2的路径走下去，你只有两个选项 {0,3} （因为你不能在左边的第二个数字中使用1而2是已经使用过（你可以从你的选择列表中弹出2））等等。

在这种方法中需要注意的是，如果你到达分支的末尾，3是你唯一的选择，在这种情况下，你只需删除它。

n＆gt; 10 生成所有排列，然后过滤可能会成为问题。我认为构建树会显着减少这一点。

如果需要，您可以动态构建树。您的订单可以通过您遍历树的方式来定义。