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

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;
    }
}