AS3 function producing combinations of array, no duplicates

Question

This sounds like a duplicate question, as there are several questions similar to this, but they don't specifically ask this (or I just haven't found it! :) )
I have an array, this one has two distinct elements, "a" and "b", and a length of four total elements:

    var list:Array = ["a","a","b","b"];

I'm looking for all combinations, using all elements, no duplicates.
This should yield:

    aabb
    abab
    abba
    bbaa
    baba
    baab

Searching for a solution for this has given me results similar to these:

a,b,ab,ba,aab,abb,aba, etc
or
a a b b, a a b b, a a b b, etc

Mind you, the application that would ultimately use this function would have two distinct elements, "a" and "b", and a length of 50 total elements:

    var list:Array = ["a","a","a","a","a","a","a","a","a","a",
                      "a","a","a","a","a","a","a","a","a","a",
                      "a","a","a","a","a",
                      "b","b","b","b","b","b","b","b","b","b",
                      "b","b","b","b","b","b","b","b","b","b",
                      "b","b","b","b","b"]

...so a brute force solution like I used with aabb wouldn't be feasible.

Any help, especially using AS3 code, would be appreciated, even if it is simply pointing me to the right google search :)

It is **itertools.combinations** or **itertools.permutations** in Python: https://docs.python.org/2/library/itertools.html So, you should google > **as3 combinations permutations**, there are results that seem relevant. — Organis, Mar 05 '18 at 15:21
These are permutations of [multisets](https://en.wikipedia.org/wiki/Multiset). A really fast technique is to first find all combinations of the multiset first, then subsequently use a standard `next_permutation` (like in c++) to operate on each combination. I published a package in R for doing these types of things. The source code for this task can be found [here](https://github.com/jwood000/RcppAlgos/blob/35d73b7fc9fefb2b39f1acf0cdda32f359cd5f52/src/CombinatoricsContainer.cpp#L538) (It's entirely in C++). — Joseph Wood, Mar 06 '18 at 03:59

score 0 · Answer 1 · answered Mar 06 '18 at 01:15

Here is a JavaScript answer that might get you started: Permutations in JavaScript? (they're both EcmaScript implementations so converting to ActionScript should only require minor changes)

It doesn't handle the uniqueness requirement, but it might point you in the right direction.

However, there are a few things you might need to consider first. I don't think it will be feasible to pre-compute all unique permutations upfront.

Based on this answer about unique permutations it looks like there are 50! / 25! * 25! = 126,410,606,437,752 unique permutations for 25 a's and 25 b's.

To give an idea how large that number is: if each combination was 1 byte in memory (in practice it will be more than this) then that would be: 126410606437752 bytes = 126,410.6 gigabytes in memory.

Plus, the algorithm for generating the permutations has complexity O(n!) - so it might take far too long, separate to memory constraints, to generate the list of permutations.

AS3 function producing combinations of array, no duplicates

1 Answers1