生成不包括循環轉動

Question

所有排列所以我需要一個算法來產生不包括循環轉動號碼列表的所有排列（例如，[1,2,3] == [2,3,1] == [3,1,2]）。

當序列中至少有一個唯一編號時，它非常直接，取出該唯一編號，生成其餘編號的所有排列（但對「標準」排列算法進行小修改）並添加前面的唯一號碼。

爲了生成我發現，這是必要的置換代碼更改爲排列：

def permutations(done, options) 
    permuts = [] 
    seen = [] 
    for each o in options 
     if o not in seen 
      seen.add(o) 
      permuts += permutations(done+o, options.remove(o)) 
    return permuts 

使用只有在選擇每一個獨特的編號，一旦意味着你沒有得到322的兩倍。

當沒有唯一元素時，該算法仍然輸出旋轉，例如，對於[1,1,2,2]它會輸出[1,1,2,2]，[1,2,2,1]和[1,2,1,2]，前兩個是循環旋轉。

那麼有沒有一種有效的算法，可以讓我產生所有的排列而不必事後去除循環旋轉？

如果不是，那麼刪除循環旋轉的最有效方法是什麼？

注意：這是而不是使用Python，而是C++。

Answer 1

考慮測試每個你輸出的排列，尋找一個週期性的旋轉，比你所得到的「詞法」早。如果有的話，不要退回 - 它會在其他地方被列舉出來。

選擇「唯一」第一個元素（如果存在）可幫助您優化。你知道如果你修復了第一個元素，並且它是唯一的，那麼你不可能通過旋轉來重複它。另一方面，如果沒有這種獨特的元素，只需選擇發生最少的元素。這樣你只需要檢查有第一個元素的循環旋轉。 （例如，當您生成[1,2,2,1]時 - 您只需檢查[1,1,2,2]，而不是[2,2,1,1]或[2,1,1,2 ]）。

---

OK，僞...顯然爲O（n！），我相信沒有更聰明的辦法，因爲案件 「的所有符號不同」 顯然有返回（N-1）！元素。

// generate all permutations with count[0] 0's, count[1] 1's... 
def permutations(count[]) 
    if(count[] all zero) 
     return just the empty permutation; 
    else 
     perms = []; 
     for all i with count[i] not zero 
      r = permutations(copy of count[] with element i decreased); 
      perms += i prefixed on every element of r 
     return perms; 

// generate all noncyclic permutations with count[0] 0's, count[1] 1's... 
def noncyclic(count[]) 
    choose f to be the index with smallest count[f]; 
    perms = permutations(copy of count[] with element f decreased); 
    if (count[f] is 1) 
     return perms; 
    else 
     noncyclic = []; 
     for each perm in perms 
      val = perm as a value in base(count.length); 
      for each occurence of f in perm 
       test = perm rotated so that f is first 
       tval = test as a value in base(count.length); 
       if (tval < val) continue to next perm; 
      if not skipped add perm to noncyclic; 
     return noncyclic; 

// return all noncyclic perms of the given symbols 
def main(symbols[]) 
    dictionary = array of all distinct items in symbols; 
    count = array of counts, count[i] = count of dictionary[i] in symbols 
    nc = noncyclic(count); 
    return (elements of nc translated back to symbols with the dictionary) 

Answer 2

該解決方案將涉及itertools.permutations的使用，set()和一些很好的老式集差異。請記住，查找排列的運行時間仍然是O（n！）。我的解決方案也不會在線，但可能是一個更優雅的解決方案，允許您這樣做（並且不涉及itertools.permutations）。爲此，這是完成任務的直接方式。

步驟1：使用給定的第一個元素生成循環的算法。對於列表[1, 1, 2, 2]，這將給我們[1, 1, 2, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 2, 1, 1]。

def rotations(li): 
    count = 0 
    while count < len(li): 
     yield tuple(li) 
     li = li[1:] + [li[0]] 
     count += 1 

第2步：導入itertools.permutations給我們擺在首位的排列，那麼其結果設置爲set。

from itertools import permutations 
perm = set(permutations([1, 1, 2, 2])) 

第3步：使用生成器給我們自己的集合，與循環（我們想擺脫自己的東西）。

cycles = set(((i for i in rotations([1, 1, 2, 2])))) 

第4步：對每個應用設置差異，並刪除週期。

perm = perm.difference(cycles) 

希望這會幫助你。我願意接受建議和/或更正。

Answer 3

對於所有數字都不同的置換情況，這很簡單。假設這些數字是1,2,...,n，然後生成1,2,...,n-1的所有排列，並在前面粘貼n。這給出了全集模循環旋轉的所有排列。例如，對於n=4，你會做

4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 

這可以確保1,2,3,4每個排列的一些循環旋轉出現在列表中只出現一次。

對於一般情況下，您想要多重集的排列（允許重複條目），您可以使用類似的技巧。刪除最大字母n的所有實例（類似於忽略上述示例中的4）並生成剩餘多重集的所有排列。下一步是將n以規範方式放回到排列中（類似於在上例中將4放在開頭）。

這真的只是找到所有Lyndon words的情況下產生necklaces

Answer 4

首先我會告訴容器和算法，我們會using：

#include <vector> 
#include <set> 
#include <algorithm> 
#include <iostream> 
#include <iterator> 

using std::vector; 
using std::set; 
using std::sort; 
using std::next_permutation; 
using std::copy; 
using std::ostream_iterator; 
using std::cout; 

接下來我們vector這將代表Permutation：

typedef vector<unsigned int> Permutation; 

我們需要一個比較對象來檢查是否有錯誤呃置換是一個旋轉：

struct CompareCyclicPermutationsEqual 
{ 
    bool operator()(const Permutation& lhs, const Permutation& rhs); 
}; 

而且typedef它採用循環比較對象set：

typedef set<Permutation, CompareCyclicPermutationsEqual> Permutations; 

然後主要功能是相當簡單：

int main() 
{ 
    Permutation permutation = {1, 2, 1, 2}; 
    sort(permutation.begin(). permutation.end()); 

    Permutations permutations; 

    do { 
     permutations.insert(permutation); 
    } while(next_permutation(numbers.begin(), numbers.end())) 


    copy(permutations.begin(), permutations.end(), 
     ostream_iterator<Permutation>(cout, "\n"); 

    return 0; 
} 

輸出：

1, 1, 2, 2, 
1, 2, 1, 2, 

我還沒有實施CompareCyclicPermutationsEqual呢。你也需要實現ostream& operator<<(ostream& os, const Permutation& permutation)。