Combinations with repetitions: Difference between revisions

{{Template:Combinations and permutations}}

<br><br>

 

=={{header|360 Assembly}}==

COMBREP CSECT

USING COMBREP,R13 base register

XDEC DS CL12 temp for xdeco

REGEQU

{{out}}

<pre>

</pre>

 

 

=={{header|Ada}}==

 

combinations.adb:

procedure Combinations is

 

Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count));

Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count));

 

{{out}}

{{Trans|Haskell}}

{{Trans|Python}}

-- sets of cardinality k, with

-- members drawn from xs.

script f

on |λ|(a, x)

end |λ|

end script

scanl1(go, a)

end |λ|

end script

 

 

on run

end run

 

 

 

-- Just :: a -> Maybe a

{type:"Maybe", Nothing:false, Just:x}

end Just

 

-- Nothing :: Maybe a

{type:"Maybe", Nothing:true}

end Nothing

 

-- enumFromTo :: (Int, Int) -> [Int]

end if

end enumFromTo

 

-- foldl :: (a -> b -> a) -> a -> [b] -> a

end tell

end foldl

 

-- index (!!) :: [a] -> Int -> Maybe a

end if

end |index|

 

-- map :: (a -> b) -> [a] -> [b]

end tell

end map

 

-- min :: Ord a => a -> a -> a

end if

end min

 

-- Lift 2nd class handler function into 1st class script wrapper

end if

end mReturn

 

-- repeat :: a -> Generator [a]

end tell

end scanl

 

-- scanl1 :: (a -> a -> a) -> [a] -> [a]

missing value

end if

{{Out}}

<pre>{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}</pre>

 

=={{header|AWK}}==

# syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWK

BEGIN {

exit(0)

}

<p>output:</p>

<pre>

</pre>

 

{{works with|BBC BASIC for Windows}}

list$() = "iced", "jam", "plain"

PRINT "Choices of 2 from 3:"

c% += FNchoose(n% + 1, l%, i%, m%, g%(), n$())

NEXT

{{out}}

<pre>

Total choices = 220

</pre>

 

=={{header|Bracmat}}==

This minimalist solution expresses the answer as a sum of products. Bracmat automatically normalises such expressions: terms and factors are sorted alphabetically, products containing a sum as a factor are decomposed in a sum of factors (unless the product is not itself term in a multiterm expression). Like factors are converted to a single factor with an appropriate exponent, so <code>ice^2</code> is to be understood as ice twice.

= n things thing result

. !arg:(?n.?things)

& out$(choices$(2.iced jam plain))

& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)

{{out}}

<pre>iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain

 

=={{header|C}}==

 

const char * donuts[] = { "iced", "jam", "plain", "something completely different" };

return 0;

}

{{out}}<pre>iced iced

iced jam

{{trans|PHP}}

 

using System;

using System.Collections.Generic;

}

}

{{out}}

<pre>

 

Recursive version

using System;

class MultiCombination

}

 

 

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

 

Non recursive version.

}

}

 

{{out}}

<pre>

</pre>

 

{{trans|Scheme}}

 

(defn combinations [coll k]

(when-let [[x & xs] coll]

(concat (map (partial cons x) (combinations coll (dec k)))

(combinations xs k)))))

 

{{out}}

 

=={{header|CoffeeScript}}==

combos = (arr, k) ->

return [ [] ] if k == 0

console.log combos arr, 2

console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types"

 

{{out}}

=={{header|Common Lisp}}==

The code below is a modified version of the Clojure solution.

(let ((x (car xs)))

(cond

(combinations xs (1- k)))

(combinations (cdr xs) k))))))

 

{{out}}

=={{header|Crystal}}==

{{trans|Ruby}}

puts "There are #{possible_doughnuts.size} possible doughnuts:"

possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(" and ")}

possible_doughnuts = (1..10).to_a.repeated_combinations(3)

# size returns the size of the enumerator, or nil if it can’t be calculated lazily.

{{out}}

<pre>

=={{header|D}}==

Using [http://www.graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation lexicographic next bit permutation] to generate combinations with repetitions.

 

const struct CombRep {

writeln("Ways to select 3 from 10 types is ",

CombRep(10, 3).length);

{{out}}

<pre> iced iced

 

===Short Recursive Version===

 

T[][] combsRep(T)(T[] lst, in int k) {

["iced", "jam", "plain"].combsRep(2).writeln;

10.iota.array.combsRep(3).length.writeln;

{{out}}

<pre>[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]]

=={{header|EasyLang}}==

 

items$[] = [ "iced" "jam" "plain" ]

n = len items$[]

n_results = 0

#

.

.

#

n = 10

items$[] = [ ]

n_results = 0

print ""

 

{{out}}

=={{header|EchoLisp}}==

We can use the native '''combinations/rep''' function, or use a '''combinator''' iterator, or implement the function.

;;

;; native function : combinations/rep in list.lib

→ 220

 

 

=={{header|Egison}}==

 

(define $comb/rep

(lambda [$n $xs]

 

(test (comb/rep 2 {"iced" "jam" "plain"}))

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def comb_rep(0, _), do: [[]]

def comb_rep(_, []), do: []

Enum.each(RC.comb_rep(2, s), fn x -> IO.inspect x end)

 

 

{{out}}

 

=={{header|Erlang}}==

-module(comb).

-compile(export_all).

comb_rep(N,[H|T]=S) ->

[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T).

{{out}}

<pre>

95> length(comb:comb_rep(3,lists:seq(1,10))).

220

</pre>

 

=={{header|Fortran}}==

program main

integer :: chosen(4)

 

end program main

{{out}}

<pre>

plain plain

Total = 6

</pre>

 

=={{header|GAP}}==

 

=={{header|Go}}==

===Concise recursive===

 

import "fmt"

fmt.Println(len(combrep(3,

[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))

{{out}}

<pre>

===Channel===

Using channel and goroutine, showing how to use synced or unsynced communication.

 

import "fmt"

}

fmt.Printf("\npicking 3 of 10: %d\n", count)

{{out}}

<pre>

===Multiset===

This version has proper representation of sets and multisets.

 

import (

}

fmt.Println(len(combrep(3, ten)))

{{out}}

<pre>

 

=={{header|Haskell}}==

-- list. We ignore the case where k is greater than the length of

-- the list.

main = do

print $ combsWithRep 2 ["iced", "jam", "plain"]

{{out}}

<pre>[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]]

The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, <code>combsWithRep k (x:xs)</code> involves computing <code>combsWithRep (k-1) (x:xs)</code> and <code>combsWithRep k xs</code>, both of which (separately) compute <code>combsWithRep (k-1) xs</code>. To avoid repeated computation, we can use dynamic programming:

 

combsWithRep k xs = combsBySize xs !! k

where

 

main :: IO ()

 

and another approach, using manual recursion:

where

where

 

main :: IO ()

main = do

{{Out}}

<pre>[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]]

 

Following procedure is a generator, which generates each combination of length n in turn:

# generate all combinations of length n from list L,

# including repetitions

}

end

 

Test procedure:

 

# convenience function

procedure write_list (l)

write ("There are " || count || " possible combinations of 3 from 10")

end

 

{{out}}

There are 220 possible combinations of 3 from 10

</pre>

 

=={{header|J}}==

Cartesian product, the monadic j verb { solves the problem. The rest of the code handles the various data types, order, and quantity to choose, and makes a set from the result.

 

 

Example use:

 

┌─────┬─────┐

│iced │iced │

└─────┴─────┘

#3 rcomb i.10 NB. # ways to choose 3 items from 10 with repetitions

 

===J Alternate implementation===

Considerably faster:

 

 

 

0 0

0 1

1 1

1 2

 

 

=={{header|Java}}==

'''MultiCombinationsTester.java'''

import com.objectwave.utility.*;

 

}

} // class

 

'''MultiCombinations.java'''

import com.objectwave.utility.*;

import java.util.*;

}

} // class

 

{{out}}

===ES5===

====Imperative====

<body><pre id='x'></pre><script type="application/javascript">

function disp(x) {

disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos");

disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(''), false) + " combos");

{{out}}

<pre>iced iced

 

====Functional====

 

// n -> [a] -> [[a]]

];

 

 

{{Out}}

 

[["iced", "iced"], ["iced", "jam"], ["iced", "plain"],

["jam", "jam"], ["jam", "plain"], ["plain", "plain"]],

220

 

===ES6===

{{Trans|Haskell}}

'use strict';

 

threeFromTen: length(combsWithRep(3, enumFromTo(0, 9)))

});

{{Out}}

<pre>{

 

=={{header|jq}}==

def pick(n; m): # pick n, from m onwards

if n == 0 then []

else ([.[m]] + pick(n-1; m)), pick(n; m+1)

end;

'''The task''':

(["iced", "jam", "plain"] | pick(2)),

([[range(0;10)] | pick(3)] | length) as $n

| "There are \($n) ways to pick 3 objects with replacement from 10."

{{Out}}

<pre>$ jq -n -r -c -f pick.jq

{{works with|Julia|0.6}}

 

 

l = ["iced", "jam", "plain"]

end

 

 

{{out}}

 

=={{header|Kotlin}}==

 

class CombsWithReps<T>(val m: Int, val n: Int, val items: List<T>, val countOnly: Boolean = false) {

val generic10 = "0123456789".chunked(1)

CombsWithReps(3, 10, generic10, true)

 

{{out}}

===With List Comprehension===

 

(defun combinations

(('() _)

(cons head subcoll))

(combinations tail n))))

===With Map===

 

(defun combinations

(('() _)

(combinations coll (- n 1)))

(combinations tail n))))

 

Output is the same for both:

 

> (combinations '(iced jam plain) 2)

((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))

 

=={{header|Lobster}}==

{{trans|C}}

 

// set S of length n, choose k

print count

let extra = choose(map(10):_, 3): _

{{out}}

<pre>["iced", "iced"]

 

=={{header|Lua}}==

if not nStartIndex then

nStartIndex = 1

end

end

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

 

This method will only work for small set and sample sizes (as it generates all Tuples then filters duplicates - Length[Tuples[Range[10],10]] is already bigger than Mathematica can handle).

->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}}

 

Combi[10, 3]

->220

 

 

A better method therefore:

occupation =

Flatten[Permutations /@

Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain",

"plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}}

 

Which can handle the Length[S] = 10, k=10 situation in still only seconds.

comb.count_choices shows off solutions.aggregate (which allows you to fold over solutions as they're found) rather than list.length and the factorial function.

 

:- interface.

:- import_module list, int, bag.

 

:- pred count(T::in, int::in, int::out) is det.

 

Usage:

 

:- interface.

:- import_module io.

mystery, cubed, cream_covered, explosive], 3, N),

io.write(L, !IO), io.nl(!IO),

 

{{out}}

=={{header|Nim}}==

{{trans|D}}

 

proc combsReps[T](lst: seq[T], k: int): seq[seq[T]] =

else:

lst.combsReps(k - 1).map((x: seq[T]) => lst[0] & x) &

 

echo(@["iced", "jam", "plain"].combsReps(2))

{{out}}

<pre>@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]]

{{trans|Haskell}}

 

match k, xxs with

| 0, _ -> [[]]

| k, x::xs ->

List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)

 

in the interactive loop:

===Dynamic programming===

 

let arr = Array.make (m+1) [] in

arr.(0) <- [[]];

done

) xs;

 

in the interactive loop:

 

=={{header|PARI/GP}}==

if(k==0,return([]));

if(k==1,return(vector(#v,i,concat(s,[v[i]]))));

};

xc(k,v)=binomial(#v+k-1,k);

 

=={{header|Perl}}==

The highly readable version:

sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 }

sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) }

 

printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10);

 

Prints:

 

With a module:

my $iter = combinations_with_repetition([qw/iced jam plain/], 2);

while (my $p = $iter->next) {

# Not an efficient way: generates them all in an array!

my $count =()= combinations_with_repetition([1..10],7);

 

=={{header|Phix}}==

{{out}}

<pre>

The second part suggests enough differences (collecting and showing vs only counting) to strike me as ugly and confusing.

While I could easily, say, translate the C version, I'd rather forego the extra credit and use a completely different routine:

{{out}}

<pre>

220

</pre>

 

=={{header|PHP}}==

function combos($arr, $k) {

if ($k == 0) {

$num_donut_combos = count(combos($donuts, 3));

echo "$num_donut_combos ways to order 3 donuts given 10 types";

{{out}} in the browser:

<pre>

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

 

<?php

//Author Ivan Gavryushin @dcc0

 

?>

 

=={{header|PicoLisp}}==

(cond

((=0 N) '(NIL))

'((X) (cons (car Lst) X))

(combrep (dec N) Lst) )

{{out}}

<pre>: (combrep 2 '(iced jam plain))

: (length (combrep 3 (range 1 10)))

-> 220</pre>

 

=={{header|PureBasic}}==

;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1

;combination produced includes repetition of elements and is represented by the array combIndex()

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

 

{{out}}

 

Ways to select 3 items from 10 types: 220</pre>

 

=={{header|Python}}==

>>> n, k = 'iced jam plain'.split(), 2

>>> list(combinations_with_replacement(n,k))

>>> len(list(combinations_with_replacement(range(10), 3)))

220

 

'''References:'''

{{Trans|Haskell}}

{{Works with|Python|3.7}}

 

from itertools import (accumulate, chain, islice, repeat)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')]

220</pre>

 

=={{header|Racket}}==

#lang racket

(define (combinations xs k)

(map (λ(x) (cons (first xs) x))

(combinations xs (- k 1))))]))

 

=={{header|Raku}}==

 

{{works with|Rakudo|2016.07}}

my $k = 2;

 

 

{{out}}

 

{{trans|Haskell}}

multi combs_with_rep (0, @) { () }

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

{{out}}

<pre>(iced iced)

===version 1===

This REXX version uses a type of anonymous recursion.

call RcombN 3, 2, 'iced jam plain' /*The 1st part of Rosetta Code task. */

call RcombN -10, 3, 'Iced jam plain' /* " 2nd " " " " " */

if p==z then return .(? -1); do j=? to y; @.j=p; end /*j*/; return 0

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output}}

<pre>

recursive (taken from version 1)

Reformatted and variable names suitable for OoRexx.

debug=0

Call time 'R'

Say l

End

{{out}}

<pre>----------- 3 doughnut selection taken 2 at a time:

===version 3===

iterative (transformed from version 1)

Numeric Digits 20

debug=0

Say l

End

 

{{out}}

 

=={{header|Ring}}==

# Project : Combinations with repetitions

 

next

return aList

Output:

<pre>

=={{header|Ruby}}==

{{works with|Ruby|2.0}}

puts "There are #{possible_doughnuts.count} possible doughnuts:"

possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')}

 

# Extra credit

# size returns the size of the enumerator, or nil if it can’t be calculated lazily.

{{out}}

<pre>

plain and plain

 

</pre>

 

=={{header|Scala}}==

Scala has a combinations method in the standard library.

object CombinationsWithRepetition {

 

}

}

 

{{out}}

=={{header|Scheme}}==

{{trans|PicoLisp}}

(cond ((= k 0) '(()))

((null? lst) '())

 

(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)

{{out}}

<pre>

 

===Dynamic programming===

(define arr (make-vector (+ m 1) '()))

(vector-set! arr 0 '(()))

 

(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)

{{out}}

<pre>

=={{header|Sidef}}==

{{trans|Perl}}

n>0 ? (^l -> map {|k| __FUNC__(n-1, l.slice(k), [a..., l[k]]) }) : a

}

cwr(2, %w(iced jam plain)).each {|a|

say a.map{ .join(' ') }.join("\n")

 

Also built-in:

 

say a.join(' ')

 

{{out}}

 

Efficient count of the total number of combinations with repetition:

{{out}}

<pre>

{{trans|Haskell}}

 

match k, xxs with

| 0, _ -> [[]]

| k, x::xs ->

List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)

 

in the interactive loop:

===Dynamic programming===

 

val arr = Array.array (m+1, [])

in

) xs;

Array.sub (arr, m)

 

in the interactive loop:

=={{header|Stata}}==

 

n = cols(v)

a = J(comb(n+k-1,k),k,v[1])

 

a = combrep(1..10,3)

 

'''Output'''

 

=={{header|Swift}}==

if n == 0 { return [[]] } else {

var combos = [[T]]()

}

}

Output:

<pre>plain and plain

 

=={{header|Tcl}}==

proc combrepl {set n {presorted no}} {

if {!$presorted} {

 

puts [combrepl {iced jam plain} 2]

{{out}}

<pre>

 

=={{header|TXR}}==

{{out}}

<pre>

</pre>

----

{{out}}

<pre>

 

=={{header|Ursala}}==

#import nat

 

#cast %gLSnX

 

{{out}}

<pre>

 

=={{header|VBScript}}==

 

Sub printc(vi,n,vs)

combine 10, 3, , False

combine 10, 7, , False

{{out}}

<pre>

</pre>

 

 

=={{header|XPL0}}==

int Count, Array(10);

 

Combos(0, 0, 3, 10, [0]);

Text(0, "Combos = "); IntOut(0, Count); CrLf(0);

 

{{out}}

=={{header|zkl}}==

{{trans|Clojure}}

if (k==1) return(seq);

if (not seq) return(T);

self.fcn(k-1,seq).apply(T.extend.fp(seq[0])).extend(self.fcn(k,seq[1,*]));

{{out}}

<pre>

 

=={{header|ZX Spectrum Basic}}==

20 DIM d$(n,5)

30 FOR i=1 TO n

90 PRINT d$(i);" ";d$(j)

100 NEXT j