Count the coins/0-1: Difference between revisions

From Rosetta Code
Content added Content deleted
m (Replaced "collect" with "toSeq" (equivalent but maybe more elegant.)
Line 357: Line 357:


Using a solver object rather than global variables.
Using a solver object rather than global variables.
<lang Nim>import math, strutils, sugar
<lang Nim>import math, sequtils, strutils


type Solver = object
type Solver = object
Line 383: Line 383:
echo "Sum $# from coins $#".format(want, coins.join(" "))
echo "Sum $# from coins $#".format(want, coins.join(" "))
var solver = Solver(want: want, width: width)
var solver = Solver(want: want, width: width)
var rindices = collect(for i in 0..coins.high: i)
var rindices = toSeq(0..coins.high)
solver.count(0, newSeq[int](), @coins, newSeq[int](), rindices)
solver.count(0, newSeq[int](), @coins, newSeq[int](), rindices)
if solver.count1 > 10:
if solver.count1 > 10:

Revision as of 16:22, 25 May 2021

Count the coins/0-1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Let say you have some coins in your wallet and you want to have a given sum.

You can use each coin zero or one time.

How many ways can you do it ?

The result should be a number.

For instance the answer is 10 when coins = [1, 2, 3, 4, 5] and sum = 6.

Task

Show the result for the following examples:

  •   coins = [1, 2, 3, 4, 5] and sum = 6
  •   coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
  •   coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
Extra
  •   Show the result of the same examples when the order you take the coins doesn't matter. For instance the answer is 3 when coins = [1, 2, 3, 4, 5] and sum = 6.
  •   Show an example of coins you used to reach the given sum and their indices. See Raku for this case.

Go

Translation of: Wren

<lang go>package main

import "fmt"

var cnt = 0 // order unimportant var cnt2 = 0 // order important var wdth = 0 // for printing purposes

func factorial(n int) int { 

   prod := 1
   for i := 2; i <= n; i++ {
       prod *= i
   }
   return prod

}

func count(want int, used []int, sum int, have, uindices, rindices []int) { 

   if sum == want {
       cnt++
       cnt2 += factorial(len(used))
       if cnt < 11 {
           uindicesStr := fmt.Sprintf("%v", uindices)
           fmt.Printf("  indices %*s => used %v\n", wdth, uindicesStr, used)
       }
   } else if sum < want && len(have) != 0 {
       thisCoin := have[0]
       index := rindices[0]
       rest := have[1:]
       rindices := rindices[1:]
       count(want, append(used, thisCoin), sum+thisCoin, rest,
           append(uindices, index), rindices)
       count(want, used, sum, rest, uindices, rindices)
   }

}

func countCoins(want int, coins []int, width int) { 

   fmt.Printf("Sum %d from coins %v\n", want, coins)
   cnt = 0
   cnt2 = 0
   wdth = -width
   rindices := make([]int, len(coins))
   for i := range rindices {
       rindices[i] = i
   }
   count(want, []int{}, 0, coins, []int{}, rindices)
   if cnt > 10 {
       fmt.Println("  .......")
       fmt.Println("  (only the first 10 ways generated are shown)")
   }
   fmt.Println("Number of ways - order unimportant :", cnt, "(as above)")
   fmt.Println("Number of ways - order important   :", cnt2, "(all perms of above indices)\n")

}

func main() { 

   countCoins(6, []int{1, 2, 3, 4, 5}, 7)
   countCoins(6, []int{1, 1, 2, 3, 3, 4, 5}, 9)
   countCoins(40, []int{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 20)

}</lang>

Output:
Sum 6 from coins [1 2 3 4 5]
  indices [0 1 2] => used [1 2 3]
  indices [0 4]   => used [1 5]
  indices [1 3]   => used [2 4]
Number of ways - order unimportant : 3 (as above)
Number of ways - order important   : 10 (all perms of above indices)

Sum 6 from coins [1 1 2 3 3 4 5]
  indices [0 1 5]   => used [1 1 4]
  indices [0 2 3]   => used [1 2 3]
  indices [0 2 4]   => used [1 2 3]
  indices [0 6]     => used [1 5]
  indices [1 2 3]   => used [1 2 3]
  indices [1 2 4]   => used [1 2 3]
  indices [1 6]     => used [1 5]
  indices [2 5]     => used [2 4]
  indices [3 4]     => used [3 3]
Number of ways - order unimportant : 9 (as above)
Number of ways - order important   : 38 (all perms of above indices)

Sum 40 from coins [1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100]
  indices [0 1 2 3 4 5 6 7 10] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 11] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 12] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 13] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 8]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 6 9]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 7 8]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 7 9]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 10 11]  => used [1 2 3 4 5 5 10 10]
  indices [0 1 2 3 4 5 10 12]  => used [1 2 3 4 5 5 10 10]
  .......
  (only the first 10 ways generated are shown)
Number of ways - order unimportant : 464 (as above)
Number of ways - order important   : 3782932 (all perms of above indices)

Julia

<lang julia>using Combinatorics

function coinsum(coins, targetsum; verbose=true) 

   println("Coins are $coins, target sum is $targetsum:")
   combos, perms = 0, 0
   for choice in combinations(coins)
       if sum(choice) == targetsum
           combos += 1
           verbose && println("$choice sums to $targetsum")
           for perm in permutations(choice)
               verbose && println("    permutation: $perm")
               perms += 1
           end
       end
   end
   println("$combos combinations, $perms permutations.\n")

end

coinsum([1, 2, 3, 4, 5], 6) coinsum([1, 1, 2, 3, 3, 4, 5], 6) coinsum([1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40, verbose=false)

</lang>

Output:
Coins are [1, 2, 3, 4, 5], target sum is 6:
[1, 5] sums to 6
    permutation: [1, 5]
    permutation: [5, 1]
[2, 4] sums to 6
    permutation: [2, 4]
    permutation: [4, 2]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
3 combinations, 10 permutations.

Coins are [1, 1, 2, 3, 3, 4, 5], target sum is 6:
[1, 5] sums to 6
    permutation: [1, 5]
    permutation: [5, 1]
[1, 5] sums to 6
    permutation: [1, 5]
    permutation: [5, 1]
[2, 4] sums to 6
    permutation: [2, 4]
    permutation: [4, 2]
[3, 3] sums to 6
    permutation: [3, 3]
    permutation: [3, 3]
[1, 1, 4] sums to 6
    permutation: [1, 1, 4]
    permutation: [1, 4, 1]
    permutation: [1, 1, 4]
    permutation: [1, 4, 1]
    permutation: [4, 1, 1]
    permutation: [4, 1, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
9 combinations, 38 permutations.

Coins are [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], target sum is 40:
464 combinations, 3782932 permutations.

MiniZinc

coins = [1, 2, 3, 4, 5] and sum = 6

<lang MiniZinc> %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e}; array[Items] of int: weight=[1,2,3,4,5]; var set of Items: selected; var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=6; </lang>

Output:
selected = {a, b, c};
----------
selected = {a, e};
----------
selected = {b, d};
----------
==========
%%%mzn-stat: initTime=0
%%%mzn-stat: solveTime=0.001
%%%mzn-stat: solutions=3
%%%mzn-stat: variables=21
%%%mzn-stat: propagators=31
%%%mzn-stat: propagations=236
%%%mzn-stat: nodes=11
%%%mzn-stat: failures=3
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=3
%%%mzn-stat-end
Finished in 172msec
coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6

<lang MiniZinc> %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e,f,g}; array[Items] of int: weight=[1,1,2,3,3,4,5]; var set of Items: selected; var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=6; </lang>

Output:
selected = {a, b, f};
----------
selected = {a, c, d};
----------
selected = {a, c, e};
----------
selected = {a, g};
----------
selected = {b, c, d};
----------
selected = {b, c, e};
----------
selected = {b, g};
----------
selected = {c, f};
----------
selected = {d, e};
----------
==========
%%%mzn-stat: initTime=0
%%%mzn-stat: solveTime=0.001
%%%mzn-stat: solutions=9
%%%mzn-stat: variables=29
%%%mzn-stat: propagators=43
%%%mzn-stat: propagations=820
%%%mzn-stat: nodes=35
%%%mzn-stat: failures=9
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=4
%%%mzn-stat-end
Finished in 187msec
coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40

<lang MiniZinc> %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}; array[Items] of int: weight=[1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100]; var set of Items: selected; var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=40; </lang>

Output:
selected = {a, b, c, d, e, f, g, h, k};
----------
selected = {a, b, c, d, e, f, g, h, l};
----------
[ 0 more solutions ]
selected = {a, b, c, d, e, f, g, h, m};
----------
[ 1 more solutions ]
selected = {a, b, c, d, e, f, g, i};
----------
[ 3 more solutions ]
selected = {a, b, c, d, e, f, k, l};
----------
[ 7 more solutions ]
selected = {a, b, c, d, e, g, k, l};
----------
[ 15 more solutions ]
selected = {a, b, c, d, e, j, k};
----------
[ 31 more solutions ]
selected = {a, b, c, d, g, h, l, n};
----------
[ 63 more solutions ]
selected = {a, d, e, h, i, l};
----------
[ 127 more solutions ]
selected = {b, c, e, l, m, n};
----------
[ 206 more solutions ]
selected = {k, l, m, n};
----------
==========
%%%mzn-stat: initTime=0.001
%%%mzn-stat: solveTime=0.011
%%%mzn-stat: solutions=464
%%%mzn-stat: variables=65
%%%mzn-stat: propagators=91
%%%mzn-stat: propagations=122926
%%%mzn-stat: nodes=4203
%%%mzn-stat: failures=1638
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=13
%%%mzn-stat-end
Finished in 207msec

Nim

Translation of: Go

Using a solver object rather than global variables. <lang Nim>import math, sequtils, strutils

type Solver = object 

 want: Positive
 count1: Natural
 count2: Natural
 width: Natural

proc count(solver: var Solver; sum: int; used, have, uindices, rindices: seq[int]) = 

 if sum == solver.want:
   inc solver.count1
   inc solver.count2, fac(used.len)
   if solver.count1 < 11:
     let uindiceStr = ($uindices.join(" ")).alignLeft(solver.width)
     echo "  indices $1  →  used $2".format(uindiceStr, used.join(" "))
 elif sum < solver.want and have.len != 0:
   let thisCoin = have[0]
   let index = rindices[0]
   let rest = have[1..^1]
   let rindices = rindices[1..^1]
   solver.count(sum + thisCoin, used & thisCoin, rest, uindices & index, rindices)
   solver.count(sum, used, rest, uindices, rindices)

proc countCoins(want: int; coins: openArray[int]; width: int) = 

 echo "Sum $# from coins $#".format(want, coins.join(" "))
 var solver = Solver(want: want, width: width)
 var rindices = toSeq(0..coins.high)
 solver.count(0, newSeq[int](), @coins, newSeq[int](), rindices)
 if solver.count1 > 10:
   echo "  ......."
   echo "  (only the first 10 ways generated are shown)"
 echo "Number of ways – order unimportant : ", solver.count1, " (as above)"
 echo "Number of ways – order important   : ", solver.count2, " (all perms of above indices)\n"

when isMainModule: 

 countCoins(6, [1, 2, 3, 4, 5], 5)
 countCoins(6, [1, 1, 2, 3, 3, 4, 5], 7)
 countCoins(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)</lang>
Output:
Sum 6 from coins 1 2 3 4 5
  indices 0 1 2  →  used 1 2 3
  indices 0 4    →  used 1 5
  indices 1 3    →  used 2 4
Number of ways – order unimportant : 3 (as above)
Number of ways – order important   : 10 (all perms of above indices)

Sum 6 from coins 1 1 2 3 3 4 5
  indices 0 1 5    →  used 1 1 4
  indices 0 2 3    →  used 1 2 3
  indices 0 2 4    →  used 1 2 3
  indices 0 6      →  used 1 5
  indices 1 2 3    →  used 1 2 3
  indices 1 2 4    →  used 1 2 3
  indices 1 6      →  used 1 5
  indices 2 5      →  used 2 4
  indices 3 4      →  used 3 3
Number of ways – order unimportant : 9 (as above)
Number of ways – order important   : 38 (all perms of above indices)

Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
  indices 0 1 2 3 4 5 6 7 10  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 11  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 12  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 13  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 8     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 6 9     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 7 8     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 7 9     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 10 11   →  used 1 2 3 4 5 5 10 10
  indices 0 1 2 3 4 5 10 12   →  used 1 2 3 4 5 5 10 10
  .......
  (only the first 10 ways generated are shown)
Number of ways – order unimportant : 464 (as above)
Number of ways – order important   : 3782932 (all perms of above indices)

Pascal

first count all combinations by brute force.Order is important.Modified nQueens.
Next adding weigths by index.
Using Phix wording 'silly'. <lang pascal>program Coins0_1; {$IFDEF FPC} 

  {$MODE DELPHI}
  {$OPTIMIZATION ON,ALL}

{$ELSE} 

 {$Apptype console}

{$ENDIF}

uses 

 sysutils;// TDatetime

const 

 coins1 :array[0..4] of byte = (1, 2, 3, 4, 5);
 coins2 :array[0..6] of byte = (1, 1, 2, 3, 3, 4, 5);
 coins3 :array[0..15] of byte = (1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100);
 nmax = High(Coins3);

type {$IFNDEF FPC} 

 NativeInt = Int32;

{$ENDIF} 

 tFreeCol = array[0..nmax] of Int32;

var 

 FreeIdx,
 IdxWeight : tFreeCol;
 n,
 gblCount : nativeUInt;

procedure AddNextWeight(Row,sum:nativeInt); //order is important var 

 i,Col,Weight : nativeInt;

begin 

 IF row <= n then
 begin
   For i := row to n do
   begin
     Col := FreeIdx[i];
     Weight:= IdxWeight[col];
     IF Sum+Weight <= 0 then
     Begin
       Sum +=Weight;
       If Sum = 0 then
       Begin
         Sum -=Weight;
         inc(gblCount);
       end
       else
       begin
         FreeIdx[i] := FreeIdx[Row];
         FreeIdx[Row] := Col;

         AddNextWeight(Row+1,sum);
         //Undo
         Sum -=Weight;
         FreeIdx[Row] := FreeIdx[i];
         FreeIdx[i] := Col;
       end;
     end;
   end;
 end;

end;

procedure CheckBinary(n,MaxIdx,Sum:NativeInt); //order is not important Begin 

 if sum = 0 then
   inc(gblcount);
 If (sum < 0) AND (n <= MaxIdx) then
 Begin
   //test next sum 
   CheckBinary(n+1,MaxIdx,Sum);// add nothing
   CheckBinary(n+1,MaxIdx,Sum+IdxWeight[n]);//or the actual index
 end;

end;

procedure CheckAll(i,MaxSum:NativeInt); Begin 

 n := i;
 gblCount := 0;
 AddNextWeight(0,-MaxSum);
 Write(MaxSum:6,gblCount:12);
 gblCount := 0;
 CheckBinary(0,i,-MaxSum);
 WriteLn(gblCount:12);

end;

var 

 i: nativeInt;

begin 

 writeln('sum':6,'very silly':12,'silly':12);
 For i := 0 to High(coins1) do
 Begin
   FreeIdx[i] := i;
   IdxWeight[i] := coins1[i];
 end;
 CheckAll(High(coins1),6);

 For i := 0 to High(coins2) do
 Begin
   FreeIdx[i] := i;
   IdxWeight[i] := coins2[i];
 end;
 CheckAll(High(coins2),6);

 For i := 0 to High(coins3) do
 Begin
   FreeIdx[i] := i;
   IdxWeight[i] := coins3[i];
 end;
 CheckAll(High(coins3),40);

end. </lang>

Output:
   sum  very silly       silly
     6          10           3
     6          38           9
    40     3782932         464

// real	0m0,080s ( fpc 3.2.0 -O3 -Xs AMD 2200G 3.7 Ghz )

Perl

<lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1 use warnings;

countcoins( 6, [1, 2, 3, 4, 5] ); countcoins( 6, [1, 1, 2, 3, 3, 4, 5] ); countcoins( 40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] );

my $count;

sub countcoins 

 {
 my ($want, $coins) = @_;
 print "\nsum $want coins @$coins\n";
 $count = 0;
 count($want, [], 0, $coins);
 print "Number of ways: $count\n";
 }

sub count 

 {
 my ($want, $used, $sum, $have) = @_;
 if( $sum == $want ) { $count++ }
 elsif( $sum > $want or @$have == 0 ) {}
 else
   {
   my ($thiscoin, @rest) = @$have;
   count( $want, [@$used, $thiscoin], $sum + $thiscoin, \@rest);
   count( $want, $used, $sum, \@rest);
   }
 }</lang>
Output:
sum 6 coins 1 2 3 4 5
Number of ways: 3

sum 6 coins 1 1 2 3 3 4 5
Number of ways: 9

sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
Number of ways: 464

Phix

sane way

In the second test, this counts [1,2,3] as one way to get 6, not counting the other [1,2,3] or the other [1,2,3] or the other [1,2,3]. <lang Phix>function choices(sequence coins, integer tgt, cdx=1) 

   integer count = 0
   if tgt=0 then
       count += 1
   elsif tgt>0 and cdx<=length(coins) then
       object ci = coins[cdx]
       integer {c,n} = iff(sequence(ci)?ci:{ci,1})
       for j=0 to n do
           count += choices(coins,tgt-j*c,cdx+1)
       end for
   end if
   return count

end function

constant tests = {{{1,2,3,4,5},6}, 

                 {{{1,2},2,{3,2},4,5},6},
                 {{1,2,3,4,{5,4},{15,2},{10,4},25,100},40}}

?apply(false,choices,tests)</lang>

Output:
{3,5,33}

silly way

In the second test, this counts [1,2,3] as four ways to get 6, since there are two 1s and two 3s... ("order unimportant") <lang Phix>function silly(sequence coins, integer tgt, cdx=1) 

   integer count = 0
   if tgt=0 then
       count += 1
   elsif tgt>0 and cdx<=length(coins) then
       count += silly(coins,tgt-coins[cdx],cdx+1)
       count += silly(coins,tgt,cdx+1)
   end if
   return count

end function

constant tests = {{{1,2,3,4,5},6}, 

                 {{1,1,2,3,3,4,5},6},
                 {{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}}

?apply(false,silly,tests)</lang>

Output:
{3,9,464}

very silly way

In the second test, this counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s, and 6 ways to order them ("order important") <lang Phix>function very_silly(sequence coins, integer tgt, cdx=1, taken=0) 

   integer count = 0
   if tgt=0 then
       count += factorial(taken)
   elsif tgt>0 and cdx<=length(coins) then
       count += very_silly(coins,tgt-coins[cdx],cdx+1,taken+1)
       count += very_silly(coins,tgt,cdx+1,taken)
   end if
   return count

end function

constant tests = {{{1,2,3,4,5},6}, 

                 {{1,1,2,3,3,4,5},6},
                 {{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}}

?apply(false,very_silly,tests)</lang>

Output:
{10,38,3782932}

Raku

First part is combinations filtered on a certain property. Second part (extra credit) is permutations of those combinations.

This is pretty much duplicating other tasks, in process if not wording. Even though I am adding a solution, my vote would be for deletion as it doesn't really add anything to the other tasks; Combinations, Permutations, Subset sum problem and to a large extent 4-rings or 4-squares puzzle.

<lang perl6>for <1 2 3 4 5>, 6 

  ,<1 1 2 3 3 4 5>, 6
  ,<1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100>, 40
 -> @items, $sum {

   put "\n\nHow many combinations of [{ @items.join: ', ' }] sum to $sum?";

   given ^@items .combinations.grep: { @items[$_].sum == $sum } {
       .&display;
       display .race.map( { Slip(.permutations) } ), ;
   }

}

sub display ($list, $un = 'un') { 

   put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' );
   put $list.pick(10).sort».join(', ').join: "\n"

}</lang>

Output:
How many combinations of [1, 2, 3, 4, 5] sum to 6?

Order unimportant:
Count: 3
Indices:
0, 1, 2
0, 4
1, 3

Order important:
Count: 10
Indices:
0, 1, 2
0, 2, 1
0, 4
1, 0, 2
1, 2, 0
1, 3
2, 0, 1
2, 1, 0
3, 1
4, 0


How many combinations of [1, 1, 2, 3, 3, 4, 5] sum to 6?

Order unimportant:
Count: 9
Indices:
0, 1, 5
0, 2, 3
0, 2, 4
0, 6
1, 2, 3
1, 2, 4
1, 6
2, 5
3, 4

Order important:
Count: 38
Indices (10 random examples):
0, 4, 2
1, 2, 3
1, 2, 4
1, 5, 0
1, 6
2, 1, 3
2, 1, 4
2, 4, 0
3, 2, 0
6, 0


How many combinations of [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] sum to 40?

Order unimportant:
Count: 464
Indices (10 random examples):
0, 1, 2, 3, 5, 7, 10, 11
0, 1, 2, 3, 5, 8, 12
0, 1, 2, 3, 6, 7, 11, 13
0, 3, 5, 7, 9, 13
0, 3, 9, 10, 11
1, 2, 5, 7, 9, 13
4, 5, 10, 12, 13
5, 6, 7, 9, 10
5, 6, 10, 11, 12
5, 8, 10, 12

Order important:
Count: 3782932
Indices (10 random examples):
0, 11, 3, 4, 7, 5, 6, 1, 2
1, 10, 5, 4, 6, 2, 0, 3, 7
2, 7, 13, 4, 1, 3, 5, 6, 0
2, 12, 4, 13, 10, 1
3, 0, 5, 4, 7, 13, 6, 2, 1
5, 7, 9, 4, 0, 1, 2, 3
6, 2, 7, 11, 0, 3, 5, 1, 4
10, 0, 12, 6, 5, 3, 4
13, 0, 1, 5, 7, 3, 2, 12
13, 6, 10, 1, 4, 3, 2, 0

Wren

Translation of: Perl

Well, after some huffing and puffing, the house is still standing so I thought I'd have a go at it. Based on the Perl algorithm but modified to deal with the extra credit. <lang ecmascript>import "/fmt" for Fmt import "/math" for Int

var cnt = 0 // order unimportant var cnt2 = 0 // order important var wdth = 0 // for printing purposes

var count // recursive count = Fn.new { |want, used, sum, have, uindices, rindices| 

   if (sum == want) {
       cnt = cnt + 1
       cnt2 = cnt2 + Int.factorial(used.count)
       if (cnt < 11) Fmt.print("  indices $*n => used $n", wdth, uindices, used)
   } else if (sum < want && !have.isEmpty) {
       var thisCoin = have[0]
       var index = rindices[0]
       var rest = have.skip(1).toList
       var rindices = rindices.skip(1).toList
       count.call(want, used + [thisCoin], sum + thisCoin, rest, uindices + [index], rindices)
       count.call(want, used, sum, rest, uindices, rindices)
   }

}

var countCoins = Fn.new { |want, coins, width| 

   System.print("Sum %(want) from coins %(coins)")
   cnt  = 0
   cnt2 = 0
   wdth = -width
   count.call(want, [], 0, coins, [], (0...coins.count).toList)
   if (cnt > 10) {
       System.print("  .......")
       System.print("  (only the first 10 ways generated are shown)")
   }
   System.print("Number of ways - order unimportant : %(cnt) (as above)")
   System.print("Number of ways - order important   : %(cnt2) (all perms of above indices)\n")

}

countCoins.call(6, [1, 2, 3, 4, 5], 9) countCoins.call(6, [1, 1, 2, 3, 3, 4, 5], 9) countCoins.call(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 28)</lang>

Output:
Sum 6 from coins [1, 2, 3, 4, 5]
  indices [0, 1, 2] => used [1, 2, 3]
  indices [0, 4]    => used [1, 5]
  indices [1, 3]    => used [2, 4]
Number of ways - order unimportant : 3 (as above)
Number of ways - order important   : 10 (all perms of above indices)

Sum 6 from coins [1, 1, 2, 3, 3, 4, 5]
  indices [0, 1, 5] => used [1, 1, 4]
  indices [0, 2, 3] => used [1, 2, 3]
  indices [0, 2, 4] => used [1, 2, 3]
  indices [0, 6]    => used [1, 5]
  indices [1, 2, 3] => used [1, 2, 3]
  indices [1, 2, 4] => used [1, 2, 3]
  indices [1, 6]    => used [1, 5]
  indices [2, 5]    => used [2, 4]
  indices [3, 4]    => used [3, 3]
Number of ways - order unimportant : 9 (as above)
Number of ways - order important   : 38 (all perms of above indices)

Sum 40 from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 10] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 11] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 12] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 13] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 8]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 6, 9]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 7, 8]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 7, 9]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 10, 11]   => used [1, 2, 3, 4, 5, 5, 10, 10]
  indices [0, 1, 2, 3, 4, 5, 10, 12]   => used [1, 2, 3, 4, 5, 5, 10, 10]
  .......
  (only the first 10 ways generated are shown)
Number of ways - order unimportant : 464 (as above)
Number of ways - order important   : 3782932 (all perms of above indices)
Retrieved from "https://rosettacode.org/wiki/Count_the_coins/0-1?oldid=306343"