Generating combinations if items can be together in one combination just once-CodePudding

Let's say I have N items. Now I want to create M-item combinations but if there already exist a combination {A,B,C} (in this case M=3), then A cannot be in another combination together with B nor C.

Example: N={1,2,3,4,5,6,7,8,9,10}, M=3, then possible combinations should be:

{1,2,3}
{4,5,6}
{7,8,9}
{10,1,2} - this is not a valid combination because 1 and 2 are already in a generated combination {1,2,3}
{10,1,4}
{2,5,8} - valid because all items were always in different combinations
...

How many combinations I can create?

How could I systematically generate such combinations?

What if I allow that two items can be together in two different combinations? So combinations {1,2,3} and {1,2,4} would be valid.

CodePudding user response：

Brute force, but pretty quick. In python, but clear on approach, I believe:

from itertools import combinations as c

data = range(1,11)

already_seen = set()
result = set()

all_combos = c(data,3)

for combo in all_combos:
    pairs = set(c(combo, 2))
    if not pairs & already_seen:
        result.add(combo)
        already_seen.update(pairs)

print(result)

# {(3, 9, 10), (3, 5, 6), (1, 2, 3), (2, 8, 10), (1, 4, 5), (2, 5, 7), (2, 4, 6), (1, 8, 9), (1, 6, 7), (3, 4, 7)}

CodePudding user response：

I suppose you can use standard combination generation algorithm, just add validation for used pairs, like this (in java, but pretty clear how to port to any other language):

import java.util.*;
public class Test {
    public static void main(String[] args) {
        generateCombinations(3, 10);
    }
    public static void generateCombinations(int m, int n) {
        var used = new HashSet<Long>();
        var combination = new HashSet<Integer>();
        for (int i = 1; i <= n; i  ) generateCombination(i, m, n, used, combination);
    }
    public static boolean generateCombination(int c, int m, int n, Set<Long> used, Set<Integer> comb) {
        for (Integer ci : comb) if (used.contains(getPair(ci.intValue(), c))) return false;
        boolean result = false;
        for (Integer ci : comb) used.add(getPair(ci.intValue(), c));
        comb.add(c);
        if (comb.size() < m) {
            for (int i = c   1; i <= n; i  ) {
                result |= generateCombination(i, m, n, used, comb);
                if (result && comb.size() >= 2) break;
            }
        } else {
            result = true;
            System.out.println(Arrays.toString(comb.toArray(new Integer[comb.size()])));
        }
        comb.remove(c);
        if (!result) for (Integer ci : comb) used.remove(getPair(ci.intValue(), c));
        return result;
    }
    public static long getPair(int a, int b) {
        return (((long) a) << 32L) | b;
    }
}

for 3-10 it generates 10 combinations and I suppose it is maximal number of subsets, feel free to prove me wrong

[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[1, 8, 9]
[2, 4, 6]
[2, 5, 7]
[2, 8, 10]
[3, 4, 7]
[3, 5, 6]
[3, 9, 10]

it should be moderately easy to extend it to support unique triplets instead of pairs, just generate string key like min(a,b,c) "_" middle(a,b,c) "_" max(a,b,c) instead of bitwise hack I used to speed up and add all from comb set into used set