CODEWITHSUNDEEP
c#
nfplee
nfplee

Reputation: 7997

Getting all the combinations in an array

Say I have the following array:

var arr = new[] { "A", "B", "C" };

How can I produce all the possible combinations that contain only two characters and no two the same (e.g. AB would be the same as BA). For example, using the above array it would produce:

AB
AC
BC

Please note that this example has been simplified. The array and the length of the string required will be greater.

I'd really appreciate if someone could help.

Upvotes: 12

Views: 29826

Answers (10)

s k
s k

Reputation: 5212

Hope this helps

    public static void Mutate (char[] Nums, int Idx = 0)
    {
        if (Idx == Nums.Length)
        {
            Console.WriteLine(string.Join(' ', Nums));
            return;
        }
        for (var i = Idx; i < Nums.Length; i++)
        {
            (Nums[Idx], Nums[i]) = (Nums[i], Nums[Idx]);
            Mutate(Nums, Idx + 1);
            (Nums[Idx], Nums[i]) = (Nums[i], Nums[Idx]);
        }
    }

Test With:

Mutate(new char[] { '1', '2', '3' });

Output:

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

Upvotes: 0

Yurii
Yurii

Reputation: 51

This code

var strs = new[] {"A", "B", "C", "D"};
var combinations = CreateCombinations(0, "", strs);
var text = string.Join(", ", combinations);

private List<string> CreateCombinations(int startIndex, string pair, string[] initialArray)
    {
        var combinations = new List<string>();
        for (int i = startIndex; i < initialArray.Length; i++)
        {
            var value = $"{pair}{initialArray[i]}";
            combinations.Add(value);
            combinations.AddRange(CreateCombinations(i + 1, value, initialArray));
        }

        return combinations;
    }

The text variable will contain

A, AB, ABC, ABCD, ABD, AC, ACD, AD, B, BC, BCD, BD, C, CD, D

Upvotes: 5

Arjan Einbu
Arjan Einbu

Reputation: 13692

Lets extend it, so maybe we can see the pattern:

string[] arr = new string[] { "A", "B", "C", "D", "E" };

//arr[0] + arr[1] = AB
//arr[0] + arr[2] = AC
//arr[0] + arr[3] = AD
//arr[0] + arr[4] = AE

//arr[1] + arr[2] = BC
//arr[1] + arr[3] = BD
//arr[1] + arr[4] = BE

//arr[2] + arr[3] = CD
//arr[2] + arr[4] = CE

//arr[3] + arr[4] = DE

I see two loops here.

  • The first (outer) loop goes from 0 to 4 (arr.Length - 1)
  • The second (inner) loop goes from the outer loops counter + 1 to 4 (arr.Length)

Now it should be easy to translate that to code!

Upvotes: 9

Adam Kewley
Adam Kewley

Reputation: 1234

Wrote an answer for a question that turned out to be marked as duplicate, pointing here.

var arr = new[] { "A", "B", "C" };

var arr2 = arr1.SelectMany(
    x => arr1.Select(
        y => x + y));

Produced the correct output when enumerated into console in VS2013. SelectMany will flatten the internal IEnumerable generated from the inner Select.

Upvotes: 0

user152108
user152108

Reputation: 31

What you are looking for is an double Loop along the lines of the following pseudo code.

for(int i = FirstElement; i<= LastElement; increment i) {
    for(j = i; j<= lastElement; increment j) {
        if(i != j) {
            print (i, j)
        }
    }
}

Upvotes: -1

Alex Martelli
Alex Martelli

Reputation: 882741

What you're asking for are combinations, not permutations (the latter term implies that order matters). Anyway, it's a classic use for recursion. In pseudo-code:

def combs(thearray, arraylen, currentindex, comblen):
  # none if there aren't at least comblen items left,
  # or comblen has gone <= 0
  if comblen > arraylen - currentindex or comblen <= 0:
    return
  # just 1 if there exactly comblen items left
  if comblen == arraylen - currentindex:
    yield thearray[currentindex:]
    return
  # else, all combs with the current item...:
  for acomb in combs(thearray, arraylen, currentindex+1, comblen-1):
    yield thearray[currentindex] + acomb
  # ...plus all combs without it:
  for acomb in combs(thearray, arraylen, currentindex+1, comblen):
    yield acomb

Upvotes: 1

stevedbrown
stevedbrown

Reputation: 8934

It's the sum of 1 to n-1 or n(n-1) / 2.

int num = n * ( n - 1 ) / 2;

Obviously you could generalize the n * ( n - 1 ) using a pair of factorials for whatever you are trying to do (string size wise).

Upvotes: 0

JSBձոգչ
JSBձոգչ

Reputation: 41388

public string[] Permute(char[] characters)
{
    List<string> strings = new List<string>();
    for (int i = 0; i < characters.Length; i++)
    {
        for (int j = i + 1; j < characters.Length; j++)
        {
            strings.Add(new String(new char[] { characters[i], characters[j] }));
        }
    }

    return strings.ToArray();
}

Upvotes: 0

Matt J
Matt J

Reputation: 45243

Since ordering does not matter, these are actually combinations and not permutations. In any case, there is some sample code here (you want the section entitled "Combinations (i.e., without Repetition)".

Upvotes: 1

Victor Hurdugaci
Victor Hurdugaci

Reputation: 28435

These should give you a starting point:
http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate
http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Upvotes: 7

Related Questions