20個元素的排列，滿足一定的規則

我必須找到滿足某些規則的20個元素的所有可能的排列組合。例如，元素1不能位於位置3,4,6,7,8,12和17，元素2不能位於位置1,2,7,10,19等等。目前，我正在使用遞歸函數來檢查所有可能的排列，並檢查規則是否滿足。這對10個元素（10個排列組合）來說效果很好，但是你可以想象這個算法不再可用於20個元素。有誰知道更有效的方法，可以跳過不需要的排列？（我假設，從20 = 2.4E18可能的排列只有1-2 Mio.將滿足規則20個元素的排列，滿足一定的規則

這是我在用的，現在（Pascal代碼中）！

procedure permu(p:feldtyp; ka:bereich); 
var 
    i,h : bereich; 
label skip; 
begin 
    if ka=teams then begin 

    //execute certain tests, skip the output part if the tests fail 
    for i:=1 to ka do if ((hh11[P[i]]+hh21[i])<>(ka-1)) or 
     ((patterns[h1[P[i]]][teams-1]=patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1])=(patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
     ((patterns[h1[P[i]]][teams-1]<>patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1])<>(patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
     ((patterns[h1[P[i]]][teams-1]<>patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1]) and (patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
     ((patterns[h1[P[i]]][teams-1]=patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-2]=patterns[h1[P[i]]][teams-3]) or (patterns[h2[i]][2]=patterns[h2[i]][3]))) or 
     ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][teams-2]) and (patterns[h2[i]][1]=patterns[h2[i]][2])) 
    then goto skip; 

    //all tests passed, write permutation 
    // ... 
    skip: 
    end 
    else begin 
    for i := ka to teams do begin 
     h := P[i]; 
     P[i] := p[ka]; 
     P[ka] := h; 
     permu(p, ka+1); 
    end; 
    end; 
end;

（「groups」是常量20和「h1」，「h2」是其他地方定義的一些數組[1..20]。此外定義了一個用於派生規則的全局二維數組「模式」。被看作是具有n行和19列的大0-1矩陣）

來源

2012-11-21 MathModOpt

像這樣proably：獲取每個元素的所有允許位置的列表，使用遞歸函數將每個元素放置在每個空閒的允許位置，然後遞歸地繼續下一個元素 – BeniBela

n!不在多項式附近，因此你的執行時間將會是由於n較大，因此急劇增加。如果在「哪些編號可以/不可以將轉換到哪個插槽」上有某種模式，那麼您可以使用其結構改進算法，但是您的問題聽起來不像那樣。

可能有一些艾滋病。首先，迭代上的數字在place--不是插槽中填寫：

的數字1, .., n中的每一個，使用插槽，他們可以在例如去的鏈接列表。編號3只能插入槽3,16,7,6中的 - 其中n = 3的鏈接列表。

維護所有n元素的「中央」陣列（直接訪問）。每當你把一個數字，比如x，放到插槽p中，你就會反轉該中央數組的第p個元素。

排序您n號碼，這樣，在列表的頂部是可以進入插槽，數量最少，並在底部的一個可以進入插槽數量最多的數量。

從列表頂部的數字開始，並繼續使用排列使用這些鏈接列表 - 將數字置於未填充的插槽。這爲您提供了最佳的解決方案，但指數時間爲。問題是指數性的。

您也可以使用子優化算法在多項式時間運行，但不一定允許所有排列。

來源

2012-11-23 04:31:48 ashley

20個元素的排列，滿足一定的規則

回答

相關問題