CODEWITHSUNDEEP
c#mathlogicpermutation
mrsubwoof
mrsubwoof

Reputation: 193

How to get all combinations with a fixed number of flags in array

here I have an array with a specific length and also a specific number of flags which have to be set. The length and number of flags can change from case to case, so they should be generic. Example:

var array = new bool[] { false, false, false, false, false, false };
var numberOfFlags = 2;

I'd now like to get all permutations / combinations which are possible, when always 2 flags have to be set. Example:

1 1 0 0 0 0
0 1 1 0 0 0
0 0 1 1 0 0

But also for example:

0 1 0 0 0 1

Or:

0 0 0 1 0 1

I simply need a way to get all possible combinations where the predefined number of flags are set. No pattern or anything, just all possible combinations. Preferrably in C#.

I'm really looking forward to an answer and thanks a lot!

Upvotes: 1

Views: 660

Answers (3)

Pepv
Pepv

Reputation: 171

The number of combinations can be calculed with:

P=(n!)/(a!·b!)

Where n is the lenght of the array, a is numberOfFlags and b is n - a.

This is a method of achieving what you want:

        bool[] array = new bool[] { false, false, false,false};
        int numberOfFlags = 1;

        int n, a, b,_n,_a,_b;
        n = array.Length;
        _n = n;
        a = numberOfFlags;
        _a = a;
        b = n - a;
        _b = b;

        //Calculate n!
        for (int i = _n - 1; i >= 1; i--)
            n = n * i;

        //Calculate a!
        for (int i = _a - 1; i >= 1; i--)
            a = a * i;

        //Calculate a!
        for (int i = _b - 1; i >= 1; i--)
            b = b * i;

        int NumberOfPermutations = n / (a * b);

------EDIT------

This code works only for an array with only 2 possible values. Imagine that we have 3 possible values, then:

n = lenght of the array

a = repetitions of the first value

b = repetitions of the second value

c = n - (a+b) = repetitions of the third value

The number of permutations could be calculed with P=(n!)/(a!·b!·c! ...) In the code you should add only some variables, some loops...et voilà

Upvotes: 0

L_J
L_J

Reputation: 2439

Just for numberOfFlags = 2 this is a simple sollution:

static void Main(string[] args)
{
    var array = new bool[] { false, false, false, false, false, false };

    var length = array.Length;
    for (int i = 0; i < length; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            var arr = (bool[])array.Clone();
            arr[i] = arr[j] = true;

            arr.ToList().ForEach(s => Console.Write((s ? 1 : 0) + " "));
            Console.WriteLine();
        }
    }
    Console.Read();
}

Output:

1 1 0 0 0 0
1 0 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
1 0 0 0 0 1
0 1 1 0 0 0
0 1 0 1 0 0
0 1 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
0 0 1 0 1 0
0 0 1 0 0 1
0 0 0 1 1 0
0 0 0 1 0 1
0 0 0 0 1 1

Upvotes: 0

Dennis_E
Dennis_E

Reputation: 8894

I found this on rosettacode.org. (I changed it a little bit). It's non-recursive. It just uses a Stack. It returns the same (modified) array every time, but that can be easily changed if needed.

public static IEnumerable<int[]> Combinations(int n, int k)
{
    var result = new int[k];
    var stack = new Stack<int>();
    stack.Push(0);
    
    while (stack.Count > 0) {
        int index = stack.Count - 1;
        int value = stack.Pop();
        
        while (value < n) {
            result[index++] = value++;
            stack.Push(value);
            
            if (index == k) {
                yield return result;
                break;
            }
        }
    }
}

Combinations(6, 2) will give:
[0,1], [0,2], [0,3], [0,4], [0,5], [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5]

Upvotes: 1

Related Questions