Some CS competition problem

unique_products.py

import os

inputstr = input('input: ')
splitted = inputstr.split()

assert len(splitted) == 2, 'Error: invalid input'
N = int(splitted[0])
M = int(splitted[1])

print('input: M = %d, N = %d' % (M, N))


def permuatate(rows, part_result, prod_set):
    if len(rows) == 0:
        return

    for i in rows[0]:
        prod_set.add(i * part_result)
        permuatate(rows[1:], i * part_result, prod_set)


def check_cand(prod_set, cand, other_rows):
    check_set = set()
    permuatate(other_rows, cand, check_set)

    # print('check: ', check_set, prod_set)
    return check_set.isdisjoint(prod_set), check_set


def get_result(M, N):
    results = [[1] for _ in range(N)]
    prod_set = set([1])

    while True:
        for i, row in enumerate(results):
            other_rows = results[:i] + results[i:]

            found = False
            for candidate in range(row[-1], M+1):
                qualified, new_set = check_cand(
                    prod_set, candidate, other_rows)
                if qualified:
                    prod_set.update(new_set)
                    row.append(candidate)
                    found = True
                    # print('found candidate for row %d: %d' % (i, candidate))
                    break
            if not found:
                return results


results = get_result(M, N)
minlen = min([len(row) for row in results])
for row in results:
    print(' '.join([str(i) for i in row[:minlen]]))