3

I have a numpy array that is roughly equivalent to:

data = ([1, 2, 3], [4, 5, 6], [7, 8, 9])

I want to find all the unique two-index combinations of these values. In other words, I want all the possible combinations without repeating a row or column index (similar to correctly solving a Sudoku puzzle). For example, the desired output would be:

output >> ([1, 5, 9], [1, 6, 8], [2, 4, 9], [2, 6, 7], [3, 4, 8], [3, 5, 7])

and this output can be represented by their corresponding indices: ([0][0],[1][1],[2][2]), ([0][0],[1][2],[2][1]), ([0][1],[1][0],[2][2]), ([0][1],[1][2],[2][0]), ([0][2],[1][0],[2][1]), ([0][2],[1][1],[2][0])

I've tried using itertools.permutations, and while it does find all the possible permutations of my data for each unique row, it does not treat each column as unique)

I want only one value from each row and each column.

I’m fairly new to python, does anyone have a suggestion of how I might do this?

Improve this question
8
  • 3
    What did you try? Commented Mar 24, 2017 at 23:21
  • 2
    Welcome to Stack Overflow. We're not a code writing service, so please review How to Ask and show us what you've tried. Commented Mar 24, 2017 at 23:23
  • take your output from itertools.permutations and pass it to the built in set() function, that will get rid of duplicates. Commented Mar 24, 2017 at 23:26
  • Thanks for the comments. I've tried calling itertools permutations on my array, but that returns all possible combinations where only the row is unique. I also began writing a recursive loop but then scrapped it early on: my real data set is very large and I need something more memory efficient. Commented Mar 25, 2017 at 19:55
  • If your real data set is very large this whole thing is bound to fail. Numbers of permutations grow very quickly. Commented Mar 25, 2017 at 20:06

1 Answer 1

Reset to default
1 
from itertools import permutations

data = ([1, 2, 3], [4, 5, 6], [7, 8, 9])

output = [[row[y] for row, y in zip(data, permutation)]
          for permutation in permutations(range(len(data)))]

EDIT: The problem has changed in the comments to only yield results that don't contain 0. Also since len(data) is 100 we can't produce all results using permutations like above and then filter them; that would take forever. They have to be correctly selected as we go, like so:

def get_nonzero_perms(data, remaining_indices=None):
    if not data:
        yield []
        return
    if remaining_indices is None:
        remaining_indices = list(range(len(data)))
    row = data[0]
    for i in remaining_indices:
        value = row[i]
        if value == 0:
            continue
        for perm in get_nonzero_perms(data[1:], [j for j in remaining_indices if j != i]):
            yield [value] + perm


for p in get_nonzero_perms(([2, 8, 0, 0], [0, 3, 9, 4], [0, 0, 5, 1], [4, 6, 0, 7])):
    print(p)

Output:

[2, 3, 5, 7]
[2, 9, 1, 6]
[2, 4, 5, 6]
[8, 9, 1, 4]
[8, 4, 5, 4]
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I hadn't thought of trying zip() in conjunction with my permutation iterable, thanks a lot!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.