如何分组N个项目？

我正在处理一组分区问题，并需要一种方法来定义所有无序桶大小的组合。给定N个元素并确切地为M个组，找到每个组大小的组合，使得组大小的总和为N.注意：存储桶的大小不能为0.如何分组N个项目？

例如，假设需要放置6个项目在3桶。我在寻找解决的办法是：

([1,2,3],[1,1,4],[2,2,2])

平等地映射这些，我使用地图功能如下：

@grouping = map { int(($items + $_)/$groups) } 0 .. $groups-1;

要获得所有组合我想某种递归函数的地方递归N的每个级别都找到数组中元素N的可能值。每个级别可以插入的符合条件的值是> = previousLevel。这是那种我在想什么，但有一定是更好的方法来做到这一点....

sub getList([email protected]){ 
    my $itemCount = shift; 
    my $groupCount = shift; 
    my @currentArray = @_; 
    my $positionToFill= @currentArray; 
    if($positionToFill == 0){ 
     my $minValue = 1; 
    } 
    else{ 
     my $minValue = currentArray[$positionToFill-1]; 
    } 
    my $currentSum = sum(@currentArray); 
    return undef if $currentSum + $minValue >= $items; 

    my @possibleCombinations =(); 
    for(my $i = $minValue; $i < $items - $currentSum; $i++){ 
     $currentArray[$positionToFill] = $i; 
     if($positionToFill == $groupCount-1){ 
      push(@possibleCombinations, \@currentArray) 
     } 
     else{ 
      push(@possibleCombinations, getList($itemCount, $groupCount, @currentArray); 
     }       
    } 
    return @currentArray; 
}

来源

2011-03-22 Jonathan

您需要告诉我们您到目前为止所做的以及您的具体问题是什么。 – Mat 2011-03-22 19:03:25

创建所有组合，然后筛选出不符合总和条件的组合。 – Ether 2011-03-22 19:05:59

@Ether：可以用于6，但不能很好地扩展 – ysth 2011-03-22 19:10:22

N组项目成M组，最终你需要一个递归函数组N- 1个（或更少）项目转换为M-1组。

sub partition { 
    # @results is a list of array references, the part of the partitions 
    # created in previous iterations 
    my ($N, $M, @results) = @_; 

    if ($M == 1) { 
     # only one group. All elements must go in this group. 
     return map [ sort {$a <=> $b} @$_, $N ], @results; 
    } 

    # otherwise, put from 1 to $N/$M items in the next group, 
    # and invoke this function recursively 
    my @new_results =(); 
    for (my $n = 1; $n <= $N/$M; $n++) { 
     push @new_results, partition($N-$n, $M-1, 
           map [ @$_, $n ] @results); 
    } 
    return @new_results; 
}

，并与像

@all_partitions = partition(6, 3, []); # [] = list with one ref to an empty array

这种方法会产生你必须过滤掉一些重复呼叫启动过程，但总体来说将是非常有效的。

来源

2011-03-22 20:20:44 mob

如果您还传递了最大值，则不会有重复。 – ysth 2011-03-23 01:02:26

如何分组N个项目？

回答

相关问题