找到没有元素保留位置的排列

我正在处理每个元素与原始位置不同的排列。我想要一个给定{输入长度，行和数字}的算法，会给我输出编号。下面是一个例子：找到没有元素保留位置的排列

如果输入长度为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

行号可能是的数量相等更大排列。在这种情况下，以余数为模数排列（在上述情况下，行模9）。

在c语言中会很棒。

（这不是家庭作业，它是为了工作，如果你必须知道，杜鹃哈希值我想随机选择我在每个阶段做的交换，看它是否比BFS更好，当表的数量。大于二）在Python

来源

2009-06-21 Eyal

这个问题真的没有一个有意义的答案，除非你在排列上定义了部分顺序。谁说0123必须在0213之前？ – 2009-06-21 16:31:24

好评泰勒。我命令排列从最小到最大，但我不关心行的顺序，只要输出只有输入的功能，并且每行都可能相同。 – Eyal 2009-06-21 16:36:34

蛮力方法（你可以用它来测试你的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-21 19:14:03 jfs

为什么不只是建立一个树遍历它？

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

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

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

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

如果需要，您可以随时构建树。您的订单可以通过您如何遍历树来定义。

来源

2009-08-31 03:02:44

找到没有元素保留位置的排列

回答

相关问题