generate all possibilities for entities in 2 collections

Question

I'm simplifying my blind spot to the following

assume you have 4 entities a, b, c and d; 2 collections x and y; possibilities could be for

(x;y) => (abcd;)(abc;d)(abd;c)(acd;b)(bcd;a)(ac;bd)(ad;bc)(ab;dc)(bc;ad)etc..

in short, i need to generate all possibilities for n entities in m collections in an efficient way

(bit more about the domain, i don't care for ordering, so (ab;cd) is essentially the same as (ba;cd) for my case use, if that's going to make it easier for you)

score 2 · Accepted Answer · answered Sep 06 '19 at 06:28

Very closely related is an answer given here, which deals with generation of all subsets. All subsets of a given sequence can be generated by tho following snippet, which is taken from there.

static IEnumerable<T[]> GetSubsets<T>(T[] set) {
bool[] state = new bool[set.Length+1];
    for (int x; !state[set.Length]; state[x] = true ) {
    yield return Enumerable.Range(0, state.Length)
                           .Where(i => state[i])
                           .Select(i => set[i])
                           .ToArray();
    for (x = 0; state[x]; state[x++] = false);
    }
}

Based on enumeration of all subsets,the desired solution can be ganerated by determining the complement as follows.

public class Partition
{
    public IEnumerable<string> First;
    public IEnemurable<string> Second;
};

var input = new string[]{ "a", "b", "c", "d" };
var subsets = Getsubsets(input);
var Partitions = new List<Partition>();
foreach (var subset in subsets)
{
    var iPart = new Partition();
    iPart.First = subset;
    iPart.Second = input.Where(iEl => false == subset.Contains(iEl));
    Partitions.Add(iPart);
}

score 1 · Answer 2 · answered Sep 06 '19 at 12:46

Here is an implementation that uses as state a BigInteger instead of a bool[] or a BitArray:

using System.Numerics;

public static IEnumerable<(T[], T[])> GetCollectionPairs<T>(T[] source)
{
    BigInteger combinations = BigInteger.One << source.Length;
    for (BigInteger i = 0; i < combinations; i++)
    {
        yield return
        (
            Enumerable.Range(0, source.Length)
            .Where(j => (i & (BigInteger.One << j)) != 0)
            .Select(j => source[j])
            .ToArray(),
            Enumerable.Range(0, source.Length)
            .Where(j => (i & (BigInteger.One << j)) == 0)
            .Select(j => source[j])
            .ToArray()
        );
    }
}

Usage example:

var items = new string[] { "A", "B", "C", "D" };
var pairs = GetCollectionPairs(items);
foreach (var pair in pairs)
{
    Console.WriteLine(
        $"({String.Join("", pair.Item1)};{String.Join("", pair.Item2)})");
}

Output:

(;ABCD)
(A;BCD)
(B;ACD)
(AB;CD)
(C;ABD)
(AC;BD)
(BC;AD)
(ABC;D)
(D;ABC)
(AD;BC)
(BD;AC)
(ABD;C)
(CD;AB)
(ACD;B)
(BCD;A)
(ABCD;)

This generates (AB;CD) and (CD;AB) as different pairs. If this is not desirable, then simply loop until i < combinations / 2 instead of i < combinations.

generate all possibilities for entities in 2 collections

2 Answers2