來生成一個具有特殊屬性的數組的過程

我有一個大小爲n的數組。只要下列性質保持各元件可以容納任何整數：來生成一個具有特殊屬性的數組的過程

1) All elements are non-negative 
2) sum(array[0,i+1])<i for 0<=i<n 
3) sum(array)=n-1

讓我們稱這種陣列的剷鬥。

我需要想出一個過程來生成下一個桶。

我們可以假設第一桶是{0,0,0...n-1}

示例：n=5，一些可能的組合是

[0 0 0 0 4]  
[0 0 0 1 3]  
[0 0 0 2 2]  
[0 0 0 3 1]  
[0 0 1 2 1]  
[0 0 2 1 1]  
[0 1 1 1 1]  
[0 1 0 0 3]  
[0 1 1 0 2]

我在未來與命中所有可能組合的程序麻煩

。任何提示/提示？（注意我想生成下一個桶，我不打算一次打印出所有可能的桶）

來源

2015-10-04 Mike

你想生成所有的排列，對設N = 5。然後在下一個桶中，所有這些排列都可以存活而不是第一桶的一部分？ – Ritesh

這不是一個家庭作業問題。無論我想出什麼，我都永遠不會像[0 1 1 0 2]這樣的東西出現在列表中。我只能得到非遞減順序的組合。 – Mike

家庭作業與否，沒有代碼，這不是一個問題。提示：抓住一些紙張，並製作n = 3的所有可能的清單。觀察你在做什麼。如果你沒有得到算法，那麼爲n = 4做一組詳盡的列表。 – msw

您可以使用簡單的回溯程序。這個想法是跟蹤當前sum和當前索引i。這可以讓你表達所需的約束。

n = 5 
a = [0] * n 


def backtrack(i, sum): 
    if i > 0 and sum > i-1: 
     return 
    if i == n: 
     if sum == n-1: 
      print(a) 
     return 
    for e in range(n-sum): 
     a[i] = e 
     backtrack(i + 1, sum+e) 

backtrack(0, 0)

test run

來源

2015-10-04 22:42:59 svs

來生成一個具有特殊屬性的數組的過程

回答

相關問題