如何对N个项目进行分组？

Question

我正在研究一个集合分区问题，需要一种方法来定义无序存储桶大小的所有组合。给定 N 个元素和恰好 M 个组，找到组大小的每种组合，使得组大小之和为 N。注意：桶的大小不能为 0。

例如，假设需要将 6 个项目放入 3 个桶中。我正在寻找的解决方案是：

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

为了平等地映射这些，我使用映射函数，如下所示：

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

为了获得所有组合，我正在考虑某种递归函数，其中递归的每个级别 N 找到元素 N 的可能值大批。每个级别可以插入的合格值是 >= previousLevel。这就是我的想法，但必须有更好的方法来做到这一点......

sub getList($$@){
    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;
}

Answer 1

要将 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

此方法将产生一些重复项，您必须过滤掉这些重复项，但总的来说，它会非常有效。