costs = np.random.random((3,4))

config = [(0,0),(1,1),(2,2),(2,3)]

config = [(0,3),(1,3),(2,3),(2,3),(2,0),(2,1),(2,2)]

n0,n1 = costs.shape

def filterfn(config):
    # (1) each row but the last should be represented in the config
    cond1 = set(l[0] for l in config if l[0]!=n0-1) == set(range(n0-1))
    # (2) each column but the last should be represented in the config
    cond2 = set(l[1] for l in config if l[1]!=n1-1) == set(range(n1-1))
    # (3) each row but the last should be represented exactly once
    cond3 = len(set(l[0] for l in config if l[0]!=n0-1))==len([l[0] for l in      config if l[0]!=n0-1])
    # (4) each column but the last should be represented exactly once
    cond4 = len(set(l[1] for l in config if l[1]!=n1-1))==len([l[1] for l in config if l[1]!=n1-1])

    return cond1 and cond2 and cond3 and cond4

configs = []
for r in range(max(s0,s1),s0+s1):
    r_configs  = itertools.combinations(itertools.product(range(n0),range(n1)),r)
    r_configs = filter(lambda config: filterfn(config), r_configs)
    configs.extend(list(r_configs))