1

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

如果输入长度为四，则 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。

行数可能大于排列数。在这种情况下，取余数模排列数（在上述情况下，行模 9）。

在c语言中会很棒。

（这不是家庭作业，是为了工作。Cuckoo hashing 如果你必须知道的话。我想随机选择我将在每个阶段进行的交换，看看当表数大于两个时它是否比 BFS 更好.)

4

2 回答 2

1

为什么不只是构建一棵树并遍历它呢？

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

那么，如果你沿着从 1 开始的路径，你只有三个选项，{0, 2, 3}。如果您在第一级中以 2 开头，则只有两个选项{0,3}（因为您不能在左侧第二个数字中使用 1 并且 2 已被使用（您可以从列表中弹出 2选择））等。

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

对于n > 10生成所有排列然后过滤可能会出现问题。我认为建造树会显着减少这一点。

如果需要，您可以即时构建树。您的顺序可以通过您遍历树的方式来定义。

于 2009-08-31T03:02:44.303 回答
0

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()
于 2009-06-21T19:14:03.493 回答