CODEWITHSUNDEEP
c#.netalgorithmlinqoptimization
Deadly Nicotine
Deadly Nicotine

Reputation: 663

Is there an efficient way to find all ordered arrangements of elements in the set S that add up to N?

Here's what I mean. Suppose S = {1, 4} and N = 5. The ordered arrangements of elements in the set S would be like

{1}, {4}, {1,1}, {1,4}, {4,1}, {4,4}, {1,1,1}, ....

and the ones that sum up to N are

{1,4}, {4, 1}, {1,1,1,1,1}

I want an algorithm that finds those efficiently.

My "brute force" way would be like

static IEnumerable<IEnumerable<int>> OrderedArrangements(IEnumerable<int> nums, int k)
{
    var singles = nums.Select(i => new int[] {i} );
    var cumulative = singles;
    for(int j = 2; j <= k; ++j)
    {
        var last = cumulative.Where(list => list.Count() == (j - 1));
        var next = from x in singles
                   from y in last
                   select x.Concat(y);
        cumulative = cumulative.Concat(next);           
    }
    return cumulative;
}

and then

int sumToN = OrderedArrangements(new int[] {1, 4}, N)
                .Where(x => x.Sum() == N);

but I'm wondering if there's an obvious and more efficient way to do this.

Upvotes: 1

Views: 98

Answers (2)

Bobas_Pett
Bobas_Pett

Reputation: 591

Just in case the above answer isn't clear enough, you could try straight forward recursion e.g.

     ...
    /       \
   (1)     (4)          
  /  \     /  \
 (1)(4)   (1)(4)

static void f(int sum, int n, String str, int[] arr){
    if (n == sum){
        Console.WriteLine(str);
        return;
    }
    if (n > sum) return;
    for (int i = 0; i < arr.Length; i++){
        f(sum, n + arr[i], str + arr[i].ToString(), arr);
    }
}

static void Main(string[] args){
    int[] arr =  { 1, 4 };
    f(5, 0, "", arr);
}

Where sum is N in your question, n is initialized to 0, str is initialized to "" and arr is S in your question.

output:

11111
14
41

Upvotes: 1

Enigmativity
Enigmativity

Reputation: 117027

This works for me:

static IEnumerable<IEnumerable<int>> OrderedArrangements(IEnumerable<int> nums, int k)
{
    return
        k <= 0
            ? new [] { Enumerable.Empty<int>() }
            : nums
                .SelectMany(
                    n => OrderedArrangements(nums, k - n),
                    (n, ns) => new [] { n }.Concat(ns))
                .Where(ns => ns.Sum() == k);
}

The result of OrderedArrangements(new [] { 1, 4 }, 5) is:

result

I ran this performance testing code:

Func<Func<IEnumerable<IEnumerable<int>>>, double> measure = f =>
{
    var sw = Stopwatch.StartNew();
    var result = f();
    sw.Stop();
    return sw.Elapsed.TotalMilliseconds;
};

var n = 200;
var a = 0.0;
var b = 0.0;
for (var i = 0; i < n; i++)
{
    a += measure(() => OrderedArrangements_A(new [] { 1, 4, 9, 13 }, 50000));
    b += measure(() => OrderedArrangements_B(new [] { 1, 4, 9, 13 }, 50000));
}

OrderedArrangements_A is the OP's code and OrderedArrangements_B is mine.

I got an average of 15.6ms for "A" and 0.004ms for "B". My code run about 3,895 times faster for this test.

Upvotes: 0

Related Questions