Skip to content

Instantly share code, notes, and snippets.

@theabbie
Created January 23, 2024 11:02
Show Gist options
  • Save theabbie/96590317234388eeb8a20cd72850ec0d to your computer and use it in GitHub Desktop.
Save theabbie/96590317234388eeb8a20cd72850ec0d to your computer and use it in GitHub Desktop.
Random Tree Generator
from random import *
def randTree(N):
edges = []
comps = [[i] for i in range(N)]
for _ in range(N - 1):
i = randint(0, len(comps) - 1)
j = randint(0, len(comps) - 2)
if j == i:
j += 1
if len(comps[i]) < len(comps[j]):
i, j = j, i
comps[i], comps[-2] = comps[-2], comps[i]
comps[j], comps[-1] = comps[-1], comps[j]
u = choice(comps[-2])
v = choice(comps[-1])
edges.append((min(u, v), max(u, v)))
while len(comps[-1]) > 0:
comps[-2].append(comps[-1].pop())
comps.pop()
return edges
for u, v in randTree(10):
print(u, v)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment