algorithm for calculating permutations using little memory?

Question

NOT ASKING FOR CODE TO ANSWER TO THIS SPECIFIC QUESTION, ASKING HOW TO APPROACH PROBLEM IN GENERAL

there's a question on codefights that asks to find all unique sums of two arrays, one size, the other quantity.

I'm using a cartesian product to determine all the possible permutations. This seems to be too much overhead. someone commented on the site that someone was able to do this in ONE for loop.

I'm looking for guidance on how to attack the problem from a cpu instead of memory approach.

int possibleSums(int[] coins, int[] quantity) {
    var bitmaps = Enumerable.Range(1, Convert
                  .ToInt32(new string('1', coins.Length), 2))
        .Select(bm => Convert.ToString(bm, 2).PadLeft(coins.Length,'0'));

    var sums = coins
        .Select((c, i) => new {
            Index = i,
            Coin = c,
            Quantity = quantity[i]
        })
        .Select(cqi => new {
            cqi.Coin,
            cqi.Index,
            cqi.Quantity,
            CoinSums = Enumerable.Range(1, cqi.Quantity)
                                .Select(s => s * cqi.Coin)
        });
    var distinctSums = new HashSet<int>();
    foreach (var map in bitmaps)
    {
        var coinsUsed = new List<IEnumerable<int>>();
        for (var bitpos = 0; bitpos < map.Length; bitpos++)
        {
            if (map[bitpos] == '1')
            {
                coinsUsed.Add(sums.First(s => s.Index == bitpos).CoinSums);
            }
        }
        var coinSums =
            CartesianProduct(coinsUsed).Select(x => x.Sum());
        foreach (var sum in coinSums)
        {
            if (!distinctSums.Contains(sum))
                distinctSums.Add(sum);
        }
    }

    return distinctSums.Count();
}

IEnumerable<IEnumerable<T>> CartesianProduct<T>( IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>()};
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => 
            from accseq in accumulator 
            from item in sequence 
            select accseq.Concat(new[] {item})                       
        );
 }

Answer 1

There are two general approaches to solve this in constant^[1] memory:

^{[1]: Technically O(n) memory where n is the length of the permutation, but this is far less than O(n · n!) which would be required to eagerly generate all permutations at once.}

1. Define a bijective mapping between the set of your permutations and the natural numbers N = {1, 2, ..., n!}. I.e. given a permutation index i ∈ N we can somehow decode that into the corresponding permutation. Then you can just increment a counter and yield the decoded permutation to generate all permutations. This seems to be possible with a “factorial number system”: https://en.wikipedia.org/wiki/Permutation#Numbering_permutations

2. Define a total order over all permutations, so that you have a concept of the “next” permutation. Starting with a known first permutation, you can yield the next permutation until you have arrived at the end. This generally requires that the permuted elements also have a total order. For example, it is possible to generate permutations in lexicographical order: https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Of these approaches, generating permutations in lexicographical order is simpler and more efficient, and is likely the approach you would use intuitively when generating permutations by hand. E.g. when permuting the set {a,b,c,d} where a < b < c < d then all permutations in lexicographical order are these (read column-wise):

abcd   bacd   cabd   dabc
abdc   badc   cadb   dacb
acbd   bcad   cbad   dbac
acdb   bcda   cbda   dbca
adbc   bdac   cdab   dcab
adcb   bdca   cdba   dcba

Answer 2

We can use individual bits in grouped in integers to compute permutations and combinations, and to store the intermediate state required to compute next. An incrementing integer can accomplish a lot. Since permutations and combinations both expand so rapidly, a relatively small number of bits can work over a fairly large search space, generating a lot of combinations or permutations.

Still, if your needs exceed the capabilities of integers (e.g. 32-bits on some processors or 64-bits on another), you'll need another approach.

The trick, though — to using more raw CPU and less memory — is to use bits in an integer data type native to the CPU, to maintain the intermediate state and let the CPU work on integer-sized groups of those bits at once. This usually means doing things in chunks of 64 bits.

So, from the CPU-perspective, you'd be better off using two 64-bit integers for 128 bits, if that covers the search space you're going for, than going to variable sized data (such as in a string type). Using string-type, variable-sized data pretty much means memory allocation and pointer manipulation.

Have a look at this combinations solution from some time ago, which packages into a class an integer/bit-based management of the state for combinations limited to sizes under 65. Permutations are a superset of combinations; however, something similar should work for them.