来生成一个具有特殊属性的数组的过程

我有一个大小为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

来生成一个具有特殊属性的数组的过程

回答

相关问题