Can I find all multisets of a given size more efficiently?

Question

Given the set of possible values ​​and the number of “digits,” I want to find each unique, unordered grouping of values. For example, let's say you have an alphabet from A, B, C. All 3-digit combinations will be:

AAA AAB ABB BBB BBC BCC CCC CCA CAA ABC 

The specific problem I'm trying to solve is a bit simpler. I am making a BlackJack game as an exercise in F # ( I posted this before ). The way I calculate manual values ​​is a list of lists of possible map values. All cards except Ace have one element in the list, but the aces can be either 1 or 11. The implementation that I came up with in this article creates a lot of redundancy. For example, 3 aces will create a list like [3; 13; 13; 13; 23; 23; 23; 33] [3; 13; 13; 13; 23; 23; 23; 33] [3; 13; 13; 13; 23; 23; 23; 33] . Right now I am taking the final list and running it through Distinct() , but it feels a bit hacked.

Linking it all together, the potential values ​​of aces (1, 11) make up the alphabet, and the number of aces in the hand determines the number of numbers. In this case, I would like the algorithm to appear with the following pattern:

 1, 1 1, 11 11,11 

Something tells me Dynamic programming , but my lack of proper terminology leaves me a bit stuck. Any help would be appreciated.

Edit

For what it's worth, I know that there are much simpler solutions to a specific problem, but as an exercise in functional programming, community is one of my goals.

Answer 1

This problem is a good brain teaser. It must be a golf code. :)

 let rec permute list count = seq { match list with | y::ys when count > 0 -> for n in permute list (count - 1) do yield Seq.map (fun li -> y::li) n yield Seq.concat (permute ys count) | y::ys -> yield Seq.singleton [] | [] -> () } 

Ace example

 permute ["1";"11"] 2 |> Seq.concat |> Seq.iter (printfn "%A") ["1"; "1"] ["1"; "11"] ["11"; "11"] 

ABC example

 permute ["A";"B";"C"] 3 |> Seq.concat |> Seq.iter (printfn "%A");; ["A"; "A"; "A"] ["A"; "A"; "B"] ["A"; "A"; "C"] ["A"; "B"; "B"] ["A"; "B"; "C"] ["A"; "C"; "C"] ["B"; "B"; "B"] ["B"; "B"; "C"] ["B"; "C"; "C"] ["C"; "C"; "C"] 

y::li is where all the coordinated work is done. You can replace it with y + li if all you need is strings. You must also yield Seq.singleton a "" insted []

Performance Update:

This problem is well remembered and gives much better performance not seen in trivial cases.

 let memoize2 f = let cache = Dictionary<_,_>() fun xy -> let ok, res = cache.TryGetValue((x, y)) if ok then res else let res = fxy cache.[(x, y)] <- res res // permute ["A";"B";"C"] 400 |> Seq.concat |> Seq.length |> printf "%A" // Real: 00:00:07.740, CPU: 00:00:08.234, GC gen0: 118, gen1: 114, gen2: 4 let rec permute = memoize2(fun list count -> seq { match list with | y::ys when count > 0 -> for n in permute list (count - 1) do yield Seq.map (fun li -> y::li) n |> Seq.cache yield Seq.concat (permute ys count) | y::ys -> yield Seq.singleton [] | [] -> () } |> Seq.cache) 

I also have a memoized kvb solution and it works 15% faster than mine.

 // permute ["A";"B";"C"] 400 |> Seq.length |> printf "%A" // Real: 00:00:06.587, CPU: 00:00:07.046, GC gen0: 87, gen1: 83, gen2: 4 let rec permute = memoize2 (fun list n -> match n with | 0 -> Seq.singleton [] | n -> seq { match list with | x::xs -> yield! permute list (n-1) |> Seq.map (fun l -> x::l) yield! permute xs n | [] -> () } |> Seq.cache) 

Answer 2

Hmm, in your case it is enough (1) to calculate Aces (let the number be N), and then (2) generate a possible general value as an understanding of the list

 { i * 11 + (N - i) * 1 } | 0 <= i <= N } 

... however you would express it in F #. No need to make real permutations, combinatorics, etc.

Answer 3

Here the half-translated translation of Thomas Pornin answers F #. Note that I do not expect this to be particularly more productive than the naive approach using distinct , but it is definitely ahead of:

 let rec splits l = function | [] -> Seq.empty | x::xs -> seq { yield [],x,xs for l,y,ys in splits xs do yield x::l,y,ys } let rec combs s = function | 0 -> Seq.singleton [] | n -> seq { for _,x,rest in splits s do for l in combs (x::rest) (n-1) do yield x::l } 

Or an option instead of a gradbot solution:

 let rec permute list = function | 0 -> Seq.singleton [] | n -> seq { match list with | x::xs -> yield! permute list (n-1) |> Seq.map (fun l -> x::l) yield! permute xs n | [] -> () } 

Answer 4

You can do this recursively. I am writing this in Java; my F # is not good enough:

 static void genCombInternal(int num, int[] base, int min, int max, Collection<int[]> dst) { if (num == 0) { dst.add(base); return; } for (int i = min; i <= max; i ++) { int[] nb = new int[base.length + 1]; System.arraycopy(base, 0, nb, 0, base.length); nb[base.length] = i; genCombInternal(num - 1, nb, i, max, dst); } } static Collection<int[]> genComb(int num, int min, int max) { Collection<int[]> d = new ArrayList<int[]>(); genCombInternal(num, new int[0], min, max, d); return d; } 

This code is not fully tested. If this works, then calling genComb(num, min, max) should generate all your "combinations" of integers num in the range from min to max (inclusive), so the two combinations returned are not equal, except for ordering.

This is very close to the code that generates the "true" combinations. The trick is in valid integers at every step: if you change i to i+1 in a recursive call, you should get mathematical combinations.

Answer 5

Given your “alphabet” of {1,11}, you basically want to generate all the “words” of length n , where n is the number of aces, so all 1 (0 or more) are on the left, and all of them are on the right. Ordering doesn't matter, it's just a simple approach to iterating through combinations that you are interested in.

In Python:

 n = 3 # number of aces hands = [] for i in range(0,n+1): hands.append([1] * (ni) + [11] * i) 

Or even simpler in Python:

 hands = [[1]*(ni) + [11]*i for i in range(0,n+1)] 

To get the total score for the hand:

 scores = [sum(hand) for hand in hands] 

A note on Python syntax, if you are unfamiliar, the brackets [] indicate a list, and [1]*x means creating a new list, which is a concatenation of x copies [1] ; i.e

 [1] * x == [1,1,1] 

if x = 3