Combinations with repetitions: Difference between revisions

=={{header|C++}}==

Non recursive version.

<lang cpp>

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

void print_vector(const vector<int> &v, size_t n, const vector<string> &s){

for (size_t i = 0; i < n; ++i)

printf("%s\t", s[v[i]].c_str());

printf("\n");

}

void combination_with_repetiton(int sabores, int bolas, const vector<string>& v_sabores){

sabores--;

vector<int> v(bolas+1, 0);

while (true){

for (int i = 0; i < bolas; ++i){ //vai um

if (v[i] > sabores){

v[i + 1] += 1;

for (int k = i; k >= 0; --k){

v[k] = v[i + 1];

}

//v[i] = v[i + 1];

}

}

if (v[bolas] > 0)

break;

print_vector(v, bolas, v_sabores);

v[0] += 1;

}

}

int main(){

vector<string> options{ "iced", "jam", "plain" };

combination_with_repetiton(3, 2, options);

return 0;

}

</lang>

{{out}}

<pre>

iced iced

jam iced

plain iced

jam jam

plain jam

plain plain

</pre>

=={{header|Perl 6}}==

One could simply generate all [[Permutations_with_repetitions#Perl_6|permutations]], and then remove "duplicates":

{{works with|Rakudo|2016.07}}

<lang perl6>my @S = <iced jam plain>;

my $k = 2;

.put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv])</lang>

{{out}}

<pre>

iced iced

iced jam

iced plain

jam jam

jam plain

plain plain

</pre>

Alternatively, a recursive solution:

{{trans|Haskell}}

<lang perl6>proto combs_with_rep (UInt, @) {*}

multi combs_with_rep (0, @) { () }

multi combs_with_rep (1, @a) { map { $_, }, @a }

multi combs_with_rep ($, []) { () }

multi combs_with_rep ($n, [$head, *@tail]) {

|combs_with_rep($n - 1, ($head, |@tail)).map({ $head, |@_ }),

|combs_with_rep($n, @tail);

}

.say for combs_with_rep( 2, [< iced jam plain >] );

# Extra credit:

sub postfix:<!> { [*] 1..$^n }

sub combs_with_rep_count ($k, $n) { ($n + $k - 1)! / $k! / ($n - 1)! }

say combs_with_rep_count( 3, 10 );</lang>

{{out}}

<pre>(iced iced)

(iced jam)

(iced plain)

(jam jam)

(jam plain)

(plain plain)

220</pre>

=={{header|PHP}}==

Non-recursive algorithm to generate all combinations with repetitons. Taken from here: [https://habrahabr.ru/post/311934/]

You must set k n variables and fill arrays b and c.

<lang PHP>

<?php

//Author Ivan Gavryushin @dcc0

$k=3;

$n=5;

//set amount of elements as in $n var

$c=array(1,2,3,4,5);

//set amount of 1 as in $k var

$b=array(1,1,1);

$j=$k-1;

//Вывод

function printt($b,$k) {

$z=0;

while ($z < $k) print $b[$z++].' ';

print '<br>';

}

printt ($b,$k);

while (1) {

//Увеличение на позиции K до N

if (array_search($b[$j]+1,$c)!==false ) {

$b[$j]=$b[$j]+1;

printt ($b,$k);

}

if ($b[$k-1]==$n) {

$i=$k-1;

//Просмотр массива справа налево

while ($i >= 0) {

//Условие выхода

if ( $i == 0 && $b[$i] == $n) break 2;

//Поиск элемента для увеличения

$m=array_search($b[$i]+1,$c);

if ($m!==false) {

$c[$m]=$c[$m]-1;

$b[$i]=$b[$i]+1;

$g=$i;

//Сортировка массива B

while ($g != $k-1) {

array_unshift ($c, $b[$g+1]);

$b[$g+1]=$b[$i];

$g++;

}

//Удаление повторяющихся значений из C

$c=array_diff($c,$b);

printt ($b,$k);

array_unshift ($c, $n);

break;

}

$i--;

}

}

}

?>

</lang>