2

I want to create all possible combinations of arrays with size (N) given that elements can be [-1, 0, 1], however it is only allowed to have at most 2 elements [-1, 1] while all others should be 0.

A recursive approach can suffice for the N<1000 however I am looking for efficient (both memory and computationally) way to generate up until N=10000.

The attempt for recursive case and result for N=6 is as follow;

def generate_combinations(N):
    elements = [-1, 0, 1]
    combinations = []
    generate_combinations_recursive(elements, N, [], 0, 0, combinations)
    return combinations


def generate_combinations_recursive(elements, repetitions, current_combination, num_nonzero, index, combinations):
    if index == repetitions:
        combinations.append(tuple(current_combination))
        return

    for element in elements:
        if element != 0:
            if num_nonzero < 2:
                generate_combinations_recursive(elements, repetitions, current_combination + [element], num_nonzero + 1,
                                                index + 1, combinations)
        else:
            generate_combinations_recursive(elements, repetitions, current_combination + [element], num_nonzero,
                                            index + 1, combinations)


combinations = generate_combinations(N=6)

Results

[(-1, -1, 0, 0, 0, 0),
 (-1, 0, -1, 0, 0, 0),
 (-1, 0, 0, -1, 0, 0),
 (-1, 0, 0, 0, -1, 0),
 (-1, 0, 0, 0, 0, -1),
 (-1, 0, 0, 0, 0, 0),
 (-1, 0, 0, 0, 0, 1),
 (-1, 0, 0, 0, 1, 0),
 (-1, 0, 0, 1, 0, 0),
 (-1, 0, 1, 0, 0, 0),
 (-1, 1, 0, 0, 0, 0),
 (0, -1, -1, 0, 0, 0),
 (0, -1, 0, -1, 0, 0),
 (0, -1, 0, 0, -1, 0),
 (0, -1, 0, 0, 0, -1),
 (0, -1, 0, 0, 0, 0),
 (0, -1, 0, 0, 0, 1),
 (0, -1, 0, 0, 1, 0),
 (0, -1, 0, 1, 0, 0),
 (0, -1, 1, 0, 0, 0),
 (0, 0, -1, -1, 0, 0),
 (0, 0, -1, 0, -1, 0),
 (0, 0, -1, 0, 0, -1),
 (0, 0, -1, 0, 0, 0),
 (0, 0, -1, 0, 0, 1),
 (0, 0, -1, 0, 1, 0),
 (0, 0, -1, 1, 0, 0),
 (0, 0, 0, -1, -1, 0),
 (0, 0, 0, -1, 0, -1),
 (0, 0, 0, -1, 0, 0),
 (0, 0, 0, -1, 0, 1),
 (0, 0, 0, -1, 1, 0),
 (0, 0, 0, 0, -1, -1),
 (0, 0, 0, 0, -1, 0),
 (0, 0, 0, 0, -1, 1),
 (0, 0, 0, 0, 0, -1),
 (0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 1),
 (0, 0, 0, 0, 1, -1),
 (0, 0, 0, 0, 1, 0),
 (0, 0, 0, 0, 1, 1),
 (0, 0, 0, 1, -1, 0),
 (0, 0, 0, 1, 0, -1),
 (0, 0, 0, 1, 0, 0),
 (0, 0, 0, 1, 0, 1),
 (0, 0, 0, 1, 1, 0),
 (0, 0, 1, -1, 0, 0),
 (0, 0, 1, 0, -1, 0),
 (0, 0, 1, 0, 0, -1),
 (0, 0, 1, 0, 0, 0),
 (0, 0, 1, 0, 0, 1),
 (0, 0, 1, 0, 1, 0),
 (0, 0, 1, 1, 0, 0),
 (0, 1, -1, 0, 0, 0),
 (0, 1, 0, -1, 0, 0),
 (0, 1, 0, 0, -1, 0),
 (0, 1, 0, 0, 0, -1),
 (0, 1, 0, 0, 0, 0),
 (0, 1, 0, 0, 0, 1),
 (0, 1, 0, 0, 1, 0),
 (0, 1, 0, 1, 0, 0),
 (0, 1, 1, 0, 0, 0),
 (1, -1, 0, 0, 0, 0),
 (1, 0, -1, 0, 0, 0),
 (1, 0, 0, -1, 0, 0),
 (1, 0, 0, 0, -1, 0),
 (1, 0, 0, 0, 0, -1),
 (1, 0, 0, 0, 0, 0),
 (1, 0, 0, 0, 0, 1),
 (1, 0, 0, 0, 1, 0),
 (1, 0, 0, 1, 0, 0),
 (1, 0, 1, 0, 0, 0),
 (1, 1, 0, 0, 0, 0)]
Slybot
  • 588
  • 1
  • 11
  • I altered my solution to be non-recursive and added a measurement of how long it takes for `n=1000` and an estimate of how long it will take for `n=10000`. – btilly Jun 16 '23 at 23:05

4 Answers4

2

Something like this should do the trick. Just process the output immediately, the array gets modified on the next iteration:

def generate_permutations(N):
    if N < 2:
        raise Exception('N must be 2 or greater')
        
    result = [0] * N
    
    # all zeroes
    yield result
    
    # a single 1 or -1
    for i in range(N):
        result[i] = 1
        yield result
        result[i] = -1
        yield result
        result[i] = 0
    
    # 1 and -1
    for i in range(N):
        result[i] = 1
        for j in range(N):
            if i == j:
                continue
            result[j] = -1
            yield result
            result[j] = 0
        result[i] = 0
    
    # 1, 1 or -1, -1
    for i in range(N - 1):
        for j in range(i + 1, N):
            result[i] = 1
            result[j] = 1
            yield result
            result[i] = -1
            result[j] = -1
            yield result
            result[i] = 0
            result[j] = 0

counter = 0
for p in generate_permutations(6):
    counter += 1
    print(p)

print('Found', counter, 'permutations')

It seems like there are always 2 * N^2 + 1 results.

fafl
  • 7,222
  • 3
  • 27
  • 50
1

Following this answer, you can use the sympy function sympy.utilities.iterables.multiset_permutations and create a generator function from that.

from sympy.utilities.iterables import multiset_permutations

def generate_permutations(N):
    if N < 2:
        raise ValueError("N must be >= 2.")
    
    a = [-1, 1] + [0]*(N-2)
    for p in multiset_permutations(a):
        yield p
        
    a = [-1, -1] + [0]*(N-2)
    for p in multiset_permutations(a):
        yield p
    
    a = [1, 1] + [0]*(N-2)
    for p in multiset_permutations(a):
        yield p
    
    a = [1] + [0]*(N-1)
    for p in multiset_permutations(a):
        yield p
        
    a = [-1] + [0]*(N-1)
    for p in multiset_permutations(a):
        yield p
        
    yield [0]*N

for i, p in enumerate(generate_permutations(6), 1):
    print(p)

print(f"Generated {i} permuations.")
jared
  • 4,165
  • 1
  • 8
  • 31
1

No libraries needed. No duplications. This can also be used for many minor variations on your problem.

def subset_combs(n, subset_count):
    if 0 == n:
        yield []
    elif 0 < n:
        for subset in list(subset_count.keys()):
            count = subset_count[subset]
            if 0 < count:
                subset_count[subset] = count - 1
                for comb in subset_combs(n-1, subset_count):
                    for element in subset:
                        comb.append(element)
                        yield comb
                        comb.pop()
                subset_count[subset] = count


subset_count = {
    frozenset([0]): 6,
    frozenset([-1, 1]): 2,
}

for comb in subset_combs(6, subset_count):
    print(comb)

This works and produces a correct result, but you'll get deep recursion.

So the same thing without recursion.

def subset_combs(n, subset_count):
    subsets = list(subset_count.keys())
    available = [subset_count[subsets[i]] for i in range(len(subsets))]
    solution = []
    stack = [(0, 0, False)]

    while len(stack):
        (i, j, is_tried) = stack.pop()
        if not is_tried and len(solution) == n:
            # Yield a copy for use.
            yield solution
        elif len(subsets) <= i:
            # Went off the end of subsets, abandon.
            pass
        elif len(subsets[i]) <= j:
            # Went off the end of this subset, try the next.
            stack.append((i+1, 0, False))
        elif is_tried:
            # Undo trying this.
            solution.pop()
            available[i] += 1
            # Try the next thing
            stack.append((i, j+1, False))
            stack.append((i, j+1, False))
        elif 0 < available[i]:
            # Add to the solution.
            solution.append(subsets[i][j])
            available[i] -= 1
            # Mark we tried this, and start over on the next.
            stack.append((i, j, True))
            stack.append((0, 0, False))
        else:
            # Try the next subset because we can't try this one.
            stack.append((i+1, 0, False))

n = 6
subset_count = {
    (0,):     n,
    (-1, 1,): 2,
}
for comb in subset_combs(n, subset_count):
    print(comb)

When I modify the last to just count the solutions and use pypy, it runs for n = 1000 in under 2 minutes. And it runs for 10000 as well, but that likely will take a day to finish.

btilly
  • 43,296
  • 3
  • 59
  • 88
  • is your code really cubic, as your estimation is indicating? because the output shown in the question is clearly quadratic, unless I'm missing something. – Will Ness Jul 11 '23 at 08:24
  • @WillNess You're probably missing that each of `O(n^2)` solutions takes `O(n)` work. On average the last `n/3` of the array is a string of `0`s shared with no other solution. So yes, this is cubic. – btilly Jul 11 '23 at 20:02
  • no, the work is shared. (I'm referring to your first snippet only). after the first result is returned, to make the next result it only takes one pop and one append. unless `yield` copies its argument when yielding it, in which case each solution would take `O(n^2)` time. Have you tried running your code at twice the size and see the ratio of run times, is it 4, or is it 8? – Will Ness Jul 12 '23 at 19:10
  • ah, I see what you mean. you build the result element by element, yes, so adding `n/3` 0s indeed takes `n/3` time. you probably need to switch to mutable arrays. – Will Ness Jul 12 '23 at 19:35
0

In the end, I found the following code efficient based on the ideas given by the community. As reference;

import itertools
import numpy as np

class TreeMatrixGenerator:
    def __init__(self, N):
        self.N = N
        self.dyadN = int((self.N*(self.N-1))/2)

   def iterativeGeneration(self, nonZeroElement=2):
        zero_sequence = np.zeros((1, self.dyadN,), dtype=np.int8)

        # [1] & [-1] & [1,1] & [-1,-1]
        if nonZeroElement == 1:
            indices = list(range(self.dyadN))
        else:
            indices = list(range(self.dyadN)) + list(itertools.combinations(np.arange(self.dyadN), 2))

        for idx in [-1, 1]:
            sequences = np.zeros((len(indices), self.dyadN,), dtype=np.int8)
            for idy, index in enumerate(indices):
                sequences[idy][index, ] = idx

            zero_sequence = np.concatenate([zero_sequence, sequences])

        if nonZeroElement != 1:
            # [1,-1]
            indices = list(itertools.permutations(np.arange(self.dyadN), 2))
            for idx in [(-1, 1)]:
                sequences = np.zeros((len(indices), self.dyadN,), dtype=np.int8)
                for idy, index in enumerate(indices):
                    sequences[idy][index, ] = idx
                zero_sequence = np.concatenate([zero_sequence, sequences])

        return zero_sequence
Slybot
  • 588
  • 1
  • 11