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

我正在處理每個元素與原始位置不同的排列。我想要一個給定{輸入長度，行和數字}的算法，會給我輸出編號。下面是一個例子：找到沒有元素保留位置的排列

如果輸入長度爲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

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

回答

相關問題