Tutorial :combination question



Question:

i have an array like below

int[] array = new array[n];// n may be 2,3,4  

example for N = 4

int[] array = new array[4];    array[0] = 2;  array[1] = 4;  array[2] = 6;  array[3] = 8;  

how i calculate all unrepeated combination of this array without using linq may be within?

2,4,6,8
2,4,8,6
2,8,6,4
2,6,4,6
8,6,4,2
2,4,6,8
.......
.......
.......


Solution:1

Here's a pretty flexible C# implementation using iterators.


Solution:2

Well, given that you are looking for all unrepeated combinations, that means there will be N! such combinations... (so, in your case, N! = 4! = 24 such combinations).

As I'm in the middle of posting this, dommer has pointed out a good implementation.

Just be warned that it's is going to get really slow for large values of N (since there are N! permutations).


Solution:3

Think about the two possible states of the world to see if that sheds any light.

1) There are no dupes in my array(i.e. each number in the array is unique). In this case, how many possible permutations are there?

2) There is one single dupe in the array. So, of the number of permutations that you calculated in part one, how many are just duplicates

Hmmm, lets take a three element array for simplicity

1,3,5 has how many permutations?

1,3,5

1,5,3

3,1,5

3,5,1

5,1,3

5,3,1

So six permutations

Now what happens if we change the list to say 1,5,5?

We get

1,5,5

5,1,5

5,5,1

My question to you would be, how can you express this via factorials?

Perhaps try writing out all the permutations with a four element array and see if the light bulb goes off?


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »