CODEWITHSUNDEEP
c#permutation
tobias
tobias

Reputation: 1590

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

Upvotes: 0

Views: 286

Answers (3)

Jonathan Beerhalter
Jonathan Beerhalter

Reputation: 7407

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?

Upvotes: 0

Daemonic
Daemonic

Reputation: 478

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

Upvotes: 0

dommer
dommer

Reputation: 19810

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

Upvotes: 4

Related Questions