Multiplication Combinations (Simple C#)

Question

So I have a list of ulong prime numbers, with variable lengths.

Ex: 2,5,7,3

And I want to create every multiplying combination, excluding ALL the numbers multiplied together. (2*5*7*3 in this case).

Ex: 2,3,5,6,7,10,14,15,21,30,35,42,70,105.

I have tried a couple solutions using the "foreach" loop, but I just can't seem to get it. It seems too easy. What might be an efficient way to going about this?

My main issue that I run into is that when I add a new value to the list, the "foreach" loop causes an error because I changed it. I can't think of a way around that other than do a whole bunch of new lists. It seems to me like there should be a really simple, clean solution that I am just overcomplicating.

I tried the "Build-up" approaching, multiplying the base factors together, to create larger ones and so on, and the "Build-down" approaching, starting with the large number, and then factoring it (shown in my example). This is what I tried:

List<ulong> c, f;
ulong i;
//Some code then sets c to the factors (2, 3, 5, and 7)
//i is then set to the c set multiplied together (2*3*5*7)

//if the c is a factor, divide and add it to the new list f (the final list)
foreach (ulong u in c) 
{
    if (i % u == 0)
    {
        f.Add(i/u);
        Console.WriteLine(i / u);
    }
}

// Keep on dividing the numbers down, until you get the original factors added to the list
for (int j = 0; j < f.Count -1; j++)
{
    foreach (ulong u in c)
    {
        foreach (ulong v in f)
        {
            if (v % u == 0)
            {
                if (v / u != 1 && !f.Contains(v / u))
                {
                    f.Add(v / u);
                }
            }
        }
    }
}

Expected Output with input (2 5 7 3):

• 2
• 5
• 3
• 7
• 2 * 3 = 6
• 2 * 5 = 10
• 2 * 7 = 14
• 5 * 7 = 35
• 5 * 3 = 15
• 7 * 3 = 21
• 2 * 5 * 7 = 70
• 2 * 5 * 3 = 30
• 2 * 3 * 7 = 42
• 5 * 7 * 3 = 105

Answer 1

This works to get the numbers you want:

Func<IEnumerable<ulong>, IEnumerable<ulong>> f = null;
f = xs =>
{
    if (xs.Any())
    {
        return f(xs.Skip(1))
            .SelectMany(x =>
                new [] { xs.First() * x, x });
    }
    else
    {
        return new ulong[] { 1 };
    }
};

You use it like this:

var primes = new ulong[] { 2, 5, 7, 3 };

var results = f(primes)
    .OrderBy(x => x)
    .ToArray();

results = results
    .Skip(1)
    .Take(results.Length - 2)
    .ToArray();

I had to do the Skip/Take to get rid of the two cases you wanted to avoid.

The result I get is:

If you'd like it as an (almost) one-liner here it is:

Func<IEnumerable<ulong>, IEnumerable<ulong>> f = null;
f = xs => xs.Any() ? f(xs.Skip(1)).SelectMany(x => new [] { xs.First() * x, x }) : new ulong[] { 1 };

Answer 2

The following code should give you exactly what you need with any number of items in your list

class Program
{
    static void Main(string[] args)
    {
        MultiplyFactors(new List<ulong>() { 2, 3, 5, 7 });

        Console.ReadLine();
    }

    public static void MultiplyFactors(List<ulong> numbers)
    {
        var factorCombinations = CreateSubsets(numbers.ToArray());

        foreach (var factors in factorCombinations)
        {
            // set initial result to identity value. (any number multiplied by itself is 1)
            ulong result = 1;

            // multiply all factors in combination together
            for (int i = 0; i < factors.Count(); i++)
            {
                result *= factors[i];
            }

            // Output for Display
            Console.WriteLine(String.Format("{0}={1}", String.Join("x", factors), result));

        }
    }

    private static List<T[]> CreateSubsets<T>(T[] originalArray)
    {
        // From http://stackoverflow.com/questions/3319586/getting-all-possible-permutations-from-a-list-of-numbers
        var subsets = new List<T[]>();

        for (int i = 0; i < originalArray.Length; i++)
        {
            int subsetCount = subsets.Count;
            subsets.Add(new T[] {originalArray[i]});

            for (int j = 0; j < subsetCount; j++)
            {
                T[] newSubset = new T[subsets[j].Length + 1];
                subsets[j].CopyTo(newSubset, 0);
                newSubset[newSubset.Length - 1] = originalArray[i];
                subsets.Add(newSubset);
            }
        }

        return subsets;
    }
}

This will give you the following results for your inputs of 2,3,5,7.

2=2
3=3
2x3=6
5=5
2x5=10
3x5=15
2x3x5=30
7=7
2x7=14
3x7=21
2x3x7=42
5x7=35
2x5x7=70
3x5x7=105
2x3x5x7=210

This could have been through recursion but this method was probably just as simple. The trick is creating your list of subsets. Once you have that, you simply multiply all of the elements of each subset together.