Как сгруппировать N предметов? - PullRequest
Новая
       21

Как сгруппировать N предметов?

1 голос
/ 22 марта 2011

Я работаю над проблемой разделения набора и мне нужен способ определить все комбинации неупорядоченных размеров сегментов.Учитывая 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;
}

1 Ответ

1 голос
/ 22 марта 2011

Чтобы сгруппировать 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

Этот метод создаст несколько дубликатов, которые вам придется отфильтровать, но в целом он будет довольно эффективным.

...