0

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})                       
        );
 }
2
  • This question might be a duplicate of How do I create every permutation?. In any case, that question has a very good answer worth reading.
    – amon
    Oct 13 '17 at 17:01
  • for an answer that get's this much hate it sure does get some answers. i might just copy your answers to onenote and delete the question...
    – Chris
    Oct 13 '17 at 22:02
2

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
2
  • Isn't a bijection to the naturals (one way of constructing) a total order?
    – Caleth
    Oct 13 '17 at 8:17
  • 1
    @Caleth Yes it is, but bijection to naturals is a stronger property – I think it would also work if the elements don't have an order. The idea here is to get random access to the i-th permutation, which can sometimes be very elegant. I'm mostly including it here because the general approach is useful in other circumstances. The next()` operator generating in lexicographical order does not give random access, but is a lot simpler to implement. It is likely a better solution for the concrete problem OP is facing.
    – amon
    Oct 13 '17 at 9:49
1

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.

2
  • so, let me see if i get this. instead of me using a string version of a bit map, use instead your bit enumerator? everything else i'm doing seem kosher
    – Chris
    Oct 13 '17 at 5:35
  • The solution that I had proposed in that old answer about combinations uses @amon's approach of generating the next solution from the previous solution.
    – Erik Eidt
    Oct 13 '17 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.