C# OR Javascript Permutations of two arrays multiple times

Question

I've been working, giving up and then reworking on this problem for a couple days. I've looked at a lot of different ways to go about however I either can't implement it correctly or it doesn't suit what I need it to do.

Basically: I have two arrays, prefix and suffix

 prefix = { 0, 0, 3, 8, 8, 15} 
 suffix = { 0, 3, 2, 7, 7, 9, 12, 15 }

I need to:

• Have a minimum of 3 used combined (2+1 or 1+2) and a max of 6 used (3+3).
• Not use an affix more than once (except when it's repeated (ie there's two 8's in prefix))

The end goal is to see what combinations can equal X.

eg

X = 42
3 + 8 + 8 + 2 + 9 + 12 = 42
0 + 8 + 8 + 7 + 7 + 12 = 42
| Prefix |  | Suffix |

15 + 12 + 15 = 42
0 + 15 + 0 + 12 + 15 = 42

I've tried looking into Permutations, IEnumerables, Concat's etc. but cannot find something that'll do this successfully.

These are the 'full' arrays I'm needing to work with.

public int[] Prefix = {0, 6, 6, 8, 8, 8, 8, 8, 8, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 15, 15, 18, 18, 18, 18, 18, 18, 23 };
public int[] Suffix = {0, 3, 3, 9, 11, 11, 11, 17, 18, 18, 20, 25, 25, 27, 30, 30};

Any help is appreciated, if I'm unclear about anything I'll clarify as best as possible, Thanks!

Edit: I was also suggested to run it to equate all possible outcomes and store it in a hash table to be used when the correct values are used? Not sure which would work best.

Answer 1

Taking the "OR Javascript" option...

1. Make an associative array mapping totals of the prefixes to an array of the permutations of prefixes which generate that total; then populate it.
2. Make a second associative array similar for the suffixes but only populate it with suffix permutations if expected_result - total is in the associative array for prefixes.
3. Output the valid suffixes and corresponding prefixes.

JSFIDDLE

// Inputs
var prefixes = [0, 6, 6, 8, 8, 8, 8, 8, 8, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 15, 15, 18, 18, 18, 18, 18, 18, 23],
    suffixes = [0, 3, 3, 9, 11, 11, 11, 17, 18, 18, 20, 25, 25, 27, 30, 30],
    expected_result = 42;

// Associative Arrays
var prefixTotals = {},
    suffixTotals = {},
// Functions
    addTotal     = function( map, arr, other_map ){
        var t = 0, i = 0;
        for ( ; i < arr.length; ++i )
            t += arr[i].value;
        if (   ( other_map === undefined )
            || ( ( expected_result - t ) in other_map ) )
        {
            if ( !( t in map ) )
                map[t] = [];
            map[t].push( arr );
        }
    },
    calcPermutations     = function( affixes, map, other_map ) {
        var i = 0, j, k, l = affixes.length;
        for ( ; i < l; ++i )
        {
            addTotal( map, [ { index: i, value: affixes[i] } ], other_map );
            for ( j = i+1; j < l; ++j )
            {
                addTotal( map, [ { index: i, value: affixes[i] }, { index: j, value: affixes[j] } ], other_map );
                for ( k = j+1; k < l; ++k )
                {
                    addTotal( map, [ { index: i, value: affixes[i] }, { index: j, value: affixes[j] }, { index: k, value: affixes[k] } ], other_map );
                }
            }
        }
    },
    resultToString = function( affixes ){
        var s = [];
        for ( var i = 0; i < affixes.length; ++i )
            s.push( affixes[i].index + '=>' + affixes[i].value );
        return s.join(',');
    };

calcPermutations( prefixes, prefixTotals, undefined );
calcPermutations( suffixes, suffixTotals, prefixTotals );

var i,j,k,p,s,count = 0,html=[];
for ( i in suffixTotals )
{
    s = suffixTotals[i];
    p = prefixTotals[expected_result - i];
    for ( j = 0; j < p.length; ++j )
        for ( k = 0; k < s.length; ++k )
            html.push( 'Prefixes [' + resultToString( p[j] ) + '], Suffixes [' + resultToString( s[k] ) + ']' );
    count += p.length * s.length;
}
html.unshift( 'There were ' + count + ' valid permutations:' );

document.getElementById( 'out' ).innerHTML = html.join( '<br />' );

Answer 2

As suggested you can of course nest loops till Pascal complains about his triangle, but you could also take a completely probabilistic approach if you wish :)

After all, when the brute-force solution is executing, a rogue alpha particle can flip an entire bit in the memory cells and it won't come up with the right answer anyway. (This is a joke. Don't downvote me please, let the cosmic rays hitting the SO server take care of that.)

42 ==  
  prefix.OrderBy(x => random.Next(0,prefix.Length)).Take(random.Next(1,4)).Sum() 
  + 
  suffix.OrderBy(x => random.Next(0,suffix.Length)).Take(random.Next(1,4)).Sum();

Here's a demo,

using System;
using System.Linq;

namespace WhatWasTheQuestion {
    class Program {
        static readonly int[] prefix = { 0, 0, 3, 8, 8, 15 };
        static readonly int[] suffix = { 0, 3, 2, 7, 7, 9, 12, 15 };
        static readonly Random random = new Random();

        static bool generateAndCheckCandidate(int X) {
            var prefixCandidates = prefix.OrderBy(x => random.Next(0, prefix.Length)).Take(random.Next(1, 4)).ToList();
            var suffixCandidates = suffix.OrderBy(x => random.Next(0, suffix.Length)).Take(random.Next(1, 4)).ToList();
            if (prefixCandidates.Sum() + suffixCandidates.Sum() == X) {
                Console.WriteLine(X + " = "  + String.Join("+", prefixCandidates) + "+" + String.Join("+", suffixCandidates));
                return true;
            }
            return false;
        }

        static void Main(string[] args) {
            int maxAttempts = 10000;
            while (maxAttempts > 0 && !generateAndCheckCandidate(42))
            {
                --maxAttempts;
            }
        }
    }
}
// Output:
// 42 = 8+15+0+0+7+12+0

Answer 3

This is an intuitive (albeit slow) solution using LINQ:

int[] prefixes = { 0, 0, 3, 8, 8, 15 };
int[] suffixes = { 0, 3, 2, 7, 7, 9, 12, 15 };
int target = 42;

var results =
    from prefixLength in Enumerable.Range(1, 3)
    from suffixLength in Enumerable.Range(1, 3)
    where prefixLength + suffixLength >= 3
    from prefixPermutation in prefixes.GetPermutations(prefixLength)
    from suffixPermutation in suffixes.GetPermutations(suffixLength)
    let affixPermutation = prefixPermutation.Concat(suffixPermutation)
    where affixPermutation.Sum() == target
    select string.Join(" + ", affixPermutation);

var final = results.Distinct().ToArray();

I've used a few rudimentary enumerable extensions:

public static partial class EnumerableExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> source, int length)
    {
        if (length == 0)
        {
            yield return Enumerable.Empty<T>();
            yield break;
        }

        int index = 0;
        foreach (T item in source)
        {
            IEnumerable<T> remainder = source.ExceptAt(index);
            IEnumerable<IEnumerable<T>> tails = GetPermutations(remainder, length - 1);
            foreach (IEnumerable<T> tail in tails)
                yield return tail.Prepend(item);
            index++;
        }
    }

    public static IEnumerable<T> ExceptAt<T>(this IEnumerable<T> source, int index)
    {
        return source.Take(index).Concat(source.Skip(index + 1));
    }

    public static IEnumerable<T> Prepend<T>(this IEnumerable<T> source, T first)
    {
        yield return first;
        foreach (T item in source)
            yield return item;
    }
}

Answer 4

Sorry for that big amount of code. It is not indian though and complete 100% working:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    static class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Sum: ");

            var sum = int.Parse(Console.ReadLine());

            var prefix = new[] { 1, 2, 3, 4, 5, 6 };
            var suffix = new[] { 0, 3, 2, 7, 7, 9, 12, 15 };

            foreach (var item in Solution(prefix, suffix, 1, 3, sum))
            {
                Console.WriteLine("{0} = [ {1} ] + [ {2} ]", sum, string.Join(" + ", item.Item1.Select(T => prefix[T])), string.Join(" + ", item.Item2.Select(T => suffix[T])));
            }

            Console.WriteLine("Done here. Any key to close.");
            Console.ReadKey();
        }

        public static IEnumerable<Tuple<int[], int[]>> Solution(int[] one, int[] two, int minElementCount, int maxElementCount, int sum)
        {
            if (one.Length < minElementCount || two.Length < minElementCount)
            {
                throw new Exception("Nah.");
            }

            var cacheOne = new Dictionary<int, List<int[]>>();
            var cacheTwo = new Dictionary<int, List<int[]>>();
            var result = new List<Tuple<int[], int[]>>();

            for (int countInOne = minElementCount; countInOne <= Math.Min(one.Length, maxElementCount); countInOne++)
            {
                for (int countInTwo = minElementCount; countInTwo <= Math.Min(two.Length, maxElementCount); countInTwo++)
                {
                    List<int[]> permutationsOne;
                    List<int[]> permutationsTwo;

                    if (!cacheOne.TryGetValue(countInOne, out permutationsOne))
                    {
                        permutationsOne = cacheOne[countInOne] = PermutationsIndices(one, countInOne).ToList();
                    }

                    if (!cacheTwo.TryGetValue(countInTwo, out permutationsTwo))
                    {
                        permutationsTwo = cacheTwo[countInTwo] = PermutationsIndices(two, countInTwo).ToList();
                    }

                    foreach (var permutationOne in permutationsOne)
                    {
                        var sumOne = permutationOne.Select(T => one[T]).Sum();

                        if (sumOne <= sum)
                        {
                            foreach (var permutationTwo in permutationsTwo)
                            {
                                if ((sumOne + permutationTwo.Select(T => two[T]).Sum() == sum))
                                {
                                    yield return Tuple.Create(permutationOne, permutationTwo);
                                }
                            }
                        }
                    }
                }
            }
        }
        public static IEnumerable<int[]> PermutationsIndices<T>(this T[] e, int count)
        {
            if (count > e.Length)
            {
                throw new Exception("Nah.");
            }

            return TraverseArray(e, new Stack<int>(), 0, count - 1);
        }
        public static IEnumerable<int[]> TraverseArray<T>(T[] array, Stack<int> stack, int index, int iterations)
        {
            for (int i = index; i < array.Length - iterations; i++)
            {
                stack.Push(i);

                if (iterations == 0)
                {
                    yield return stack.Reverse().ToArray();
                }
                else
                {
                    foreach (int[] item in TraverseArray(array, stack, i + 1, iterations - 1))
                    {
                        yield return item;
                    }
                }

                stack.Pop();
            }
        }
    }
}

---

So, the output for your task ...

prefix = { 0, 0, 3, 8, 8, 15 }
suffix = { 0, 3, 2, 7, 7, 9, 12, 15 }

Will be this:

Sum: 42
42 = [ 15 ] + [ 12 + 15 ]
42 = [ 8 ] + [ 7 + 12 + 15 ]
42 = [ 8 ] + [ 7 + 12 + 15 ]
42 = [ 8 ] + [ 7 + 12 + 15 ]
42 = [ 8 ] + [ 7 + 12 + 15 ]
42 = [ 15 ] + [ 0 + 12 + 15 ]
42 = [ 15 ] + [ 3 + 9 + 15 ]
42 = [ 0 + 15 ] + [ 12 + 15 ]
42 = [ 0 + 15 ] + [ 12 + 15 ]
42 = [ 3 + 15 ] + [ 9 + 15 ]
42 = [ 8 + 15 ] + [ 7 + 12 ]
42 = [ 8 + 15 ] + [ 7 + 12 ]
42 = [ 8 + 15 ] + [ 7 + 12 ]
42 = [ 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 15 ] + [ 0 + 12 + 15 ]
42 = [ 0 + 15 ] + [ 3 + 9 + 15 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 15 ] + [ 0 + 12 + 15 ]
42 = [ 0 + 15 ] + [ 3 + 9 + 15 ]
42 = [ 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 3 + 15 ] + [ 0 + 9 + 15 ]
42 = [ 3 + 15 ] + [ 3 + 9 + 12 ]
42 = [ 3 + 15 ] + [ 2 + 7 + 15 ]
42 = [ 3 + 15 ] + [ 2 + 7 + 15 ]
42 = [ 8 + 8 ] + [ 2 + 9 + 15 ]
42 = [ 8 + 8 ] + [ 7 + 7 + 12 ]
42 = [ 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 0 + 15 ] + [ 12 + 15 ]
42 = [ 0 + 3 + 15 ] + [ 9 + 15 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 3 + 15 ] + [ 9 + 15 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 7 + 12 ]
42 = [ 3 + 8 + 15 ] + [ 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 7 + 9 ]
42 = [ 8 + 8 + 15 ] + [ 2 + 9 ]
42 = [ 0 + 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 0 + 8 ] + [ 7 + 12 + 15 ]
42 = [ 0 + 0 + 15 ] + [ 0 + 12 + 15 ]
42 = [ 0 + 0 + 15 ] + [ 3 + 9 + 15 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 15 ] + [ 0 + 9 + 15 ]
42 = [ 0 + 3 + 15 ] + [ 3 + 9 + 12 ]
42 = [ 0 + 3 + 15 ] + [ 2 + 7 + 15 ]
42 = [ 0 + 3 + 15 ] + [ 2 + 7 + 15 ]
42 = [ 0 + 8 + 8 ] + [ 2 + 9 + 15 ]
42 = [ 0 + 8 + 8 ] + [ 7 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 8 ] + [ 7 + 9 + 15 ]
42 = [ 0 + 3 + 15 ] + [ 0 + 9 + 15 ]
42 = [ 0 + 3 + 15 ] + [ 3 + 9 + 12 ]
42 = [ 0 + 3 + 15 ] + [ 2 + 7 + 15 ]
42 = [ 0 + 3 + 15 ] + [ 2 + 7 + 15 ]
42 = [ 0 + 8 + 8 ] + [ 2 + 9 + 15 ]
42 = [ 0 + 8 + 8 ] + [ 7 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 0 + 7 + 12 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 0 + 8 + 15 ] + [ 3 + 7 + 9 ]
42 = [ 3 + 8 + 8 ] + [ 2 + 9 + 12 ]
42 = [ 3 + 8 + 8 ] + [ 7 + 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 0 + 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 0 + 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 2 + 7 + 7 ]
42 = [ 3 + 8 + 15 ] + [ 0 + 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 0 + 7 + 9 ]
42 = [ 3 + 8 + 15 ] + [ 2 + 7 + 7 ]
42 = [ 8 + 8 + 15 ] + [ 0 + 2 + 9 ]
Done here. Any key to close.

Answer 5

It's not a pretty solution, but it is a working one. Note how I made sure that both prefix and suffix have two zeroes at the start, so as to also include the case where you only use one or two values from that array.

    int[] prefix = { 0, 0, 3, 8, 8, 15};
    int[] suffix = { 0, 0, 3, 2, 7, 7, 9, 12, 15 };
    for(int p1 = 0; p1 < prefix.Length; p1++) {
        for(int p2 = 0; p2 < prefix.Length; p2++) {
            for(int p3 = 0; p3 < prefix.Length; p3++) {
                for(int s1 = 0; s1 < suffix.Length; s1++) {
                    for(int s2 = 0; s2 < suffix.Length; s2++) {
                        for(int s3 = 0; s3 < suffix.Length; s3++) {
                            if(prefix[p1] + prefix[p2] + prefix[p3] + suffix[s1] + suffix[s2] + suffix[s3] == 42)
                            {
                                System.Console.WriteLine(string.Format("{0} + {1} + {2} + {3} + {4} + {5} = 42", prefix[p1], prefix[p2], prefix[p3], suffix[s1], suffix[s2], suffix[s3] ));
                            }
                        }
                    }
                }
            }
        }

Answer 6

Here's another alternative which brute-forces the solution. I had to write it on .NET 3 without LINQ, so I wrote my own helper methods for summing and joining the values - hence the large amount of code. EnumerateIndices and Sum42 are doing all the work though. You can make it a lot shorter using LINQ, but I don't have access to that now so I'll leave it for you to clean this up before I accidentally introduce any errors.

public static IEnumerable<int[]> EnumerateIndices(int[] values, int length)
{
    int[] result = new int[length]; 
    int size = (int)(Math.Pow(values.Length, length));
    for(int i = 0; i < size; ++i)
    {
        int tmp = i;
        for(int j = length - 1; j >= 0; --j)
        {
            result[j] = values[tmp % values.Length];
            tmp /= values.Length;               
        }

        yield return result;
    }       
}

public static int Sum(int[] values)
{
    // Just a helper method - if you can use LINQ replace by values.Sum()
    int result = 0, size = values.Length;       
    for(int i = 0; i < size; ++i)
    {
        result += values[i];
    }
    return result;
}

public static string Join(string separator, int[] values)
{
    // Just a helper method, if you can use LINQ replace by sth like string.Join(separator, values.ToArray<string>())
    string[] stringValues = new string[values.Length];  
    int size = values.Length;
    for(int i = 0; i < size; ++i)
    {
        stringValues[i] = values[i].ToString(); 
    }
    return string.Join(separator, stringValues);
}

public static void Sum42()
{
    int[] prefix = { 0, 0, 3, 8, 8, 15};
    int[] suffix = { 0, 3, 2, 7, 7, 9, 12, 15 };

    IEnumerable<int[]> prefixes = EnumerateIndices(prefix, 3);
    IEnumerable<int[]> suffixes = EnumerateIndices(suffix, 3);
    foreach(int[] p in prefixes) {
        foreach(int[] s in suffixes) {
            if(Sum(p) + Sum(s) == 42)
            {
                System.Console.WriteLine("{0} + {1} = 42", Join(" + ", p), Join(" + ", s)); 
            }
        }
    }
}