You are given two numbers, N and G. Your goal is to split a range of integers [1..N] in equal groups of G numbers each. Each pair of numbers must be placed in exactly one group. Order does not matter.
For example, given N=9 and G=3, I could get these 12 groups:
1-2-3
1-4-5
1-6-7
1-8-9
2-4-6
2-5-8
2-7-9
3-4-9
3-5-7
3-6-8
4-7-8
5-6-9
As you can see, each possible pair of numbers from 1 to 9 is found in exactly one group. I should also mention that such grouping cannot be done for every possible combination of N and G.
I believe that this problem can be modelled best with hypergraphs: numbers are vertexes, hyperedges are groups, each hyperedge must connect exactly $G$ vertexes and no pair of vertexes can be shared by any two hyperedges.
At first, I've tried to bruteforce this problem - recursively pick valid vertexes until either running out of vertexes or finding a solution. It was way too slow, so I've started to look for ways to cut off some definitely wrong groups. If a lesser set of groups was found to be invalid, then we can predict any other set of groups which includes that one to be invalid too.
Here is the code I have so far (I hope that lack of comments is not a big concern):
#!/usr/bin/python3
# Input format:
# vertexes group_size
# Example:
# 9 3
from collections import deque
import itertools
def log(frmt, *args, **kwargs):
'Lovely logging subroutine'
if len(args)==len(kwargs)==0:
print(frmt, file=stderr)
else:
print(frmt.format(*args, **kwargs), file=stderr)
v, g = map(int, input().split())
linkcount = (v*(v-1)) // 2
if (linkcount % g) != 0:
print("INVALID GROUP SIZE")
exit
groupcount = linkcount // g
def pairs(it):
return itertools.combinations(it, 2)
# --- Vertex connections routines ---
connections = [[False for dst in range(v)] for src in range(v)]
#TODO: optimize matrix to eat up less space for large graphs
#...that is, when the freaking SLOWNESS is fixed for graph size to make any difference. >_<
def connected(a, b):
if a==b:
return True
if a>b:
a, b = b, a
# assert a<b
return connections[a][b]
def setconnect(a, b, value):
if a==b:
return False
if a>b:
a, b = b, a
# assert a<b
connections[a][b] = value
def connect(*vs):
for v1, v2 in pairs(vs):
setconnect(v1, v2, True)
def disconnect(*vs):
for v1, v2 in pairs(vs):
setconnect(v1, v2, False)
# --
# --- Failure prediction routines ---
failgroups = {}
def addFailure(groupId):
'Mark current group set as unsuccessful'
cnode = failgroups
sgroups = sorted(groups[:groupId+1])
for gp in groups:
if gp not in cnode:
cnode[gp]={}
cnode=cnode[gp]
cnode['!'] = True # Aka "end of node"
def findInSubtree(node, string, stringptr):
if stringptr>=len(string):
return False
c = string[stringptr]
if c in node:
if '!' in node[c]:
return True
else:
return findInSubtree(node[c], string, stringptr+1)
else:
return findInSubtree(node, string, stringptr+1)
def predictFailure(groupId) -> bool:
'Predict if the current group set will be unsuccessful'
sgroups = sorted(groups[:groupId+1])
return findInSubtree(failgroups, sgroups, 0)
# --
groups = [None for grp in range(groupcount)]
def debug_format_groups():
return ' '.join(('-'.join((str(i+1)) for i in group) if group else '?') for group in groups) # fluffy formatting for debugging
def try_group(groupId):
for cg in itertools.combinations(range(v), g):
groups[groupId]=cg
# Predict whether or not this group will be unsuccessful
if predictFailure(groupId):
continue
# Verify that all vertexes are unconnected
if any(connected(v1,v2) for v1,v2 in pairs(cg)):
continue
# Connect all vertexes
connect(*cg)
if groupId==groupcount-1:
return True # Last group is successful! Yupee!
elif try_group(groupId+1):
# Next group was successful, so -
return True
# Disconnect these vertexes
disconnect(*cg)
# Mark this group set as unsuccessful
addFailure(groupId)
else:
groups[groupId]=None
return False
result = try_group(0)
if result:
formatted_groups = sorted(['-'.join(str(i+1) for i in group) for group in groups])
for f in formatted_groups:
print(f)
else:
print("NO SOLUTION")
Is this an NP-complete problem? Can it be generalized as another, well-known problem, and if so - as which?
P.S. That's not a homework or contest task, if anything.
P.P.S. Sorry for my bad English, it's not my native language. I have no objections if someone edited my question for more clear phrasing. Thanks! ^^
In the meantime, I'm ready to clarify all confusing moments here.
UPDATE:
I've been thinking about it and realized than there is a better way than backtracking. First, we could build a graph where vertices represent all possible groups and edges connect all groups without common pairs of numbers. Then, each clique of power (N(N-1)/2G) would represent a solution! Unfortunately, clique problem is an NP-complete task, and generating all possible binom(N, G) groups would eat up much memory on large values of N and G. Is it possible to find a better solution?
