Deadly Nicotine - 1 year ago 65
C# Question

# 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.

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download