Get all possible combinations of rows in a matrix

Question

I'm setting up a simple sentence generator in python, to create as many word combinations as possible to describe a generic set of images involving robots. (Its a long story :D)

It outputs something like this: 'Cyborg Concept Downloadable Illustration'

Amazingly, the random generate I wrote only goes up to 255 unique combinations. Here is the script:

import numpy
from numpy import matrix
from numpy import linalg

import itertools
from pprint import pprint 
import random


m = matrix( [
    ['Robot','Cyborg','Andoid', 'Bot', 'Droid'],
    ['Character','Concept','Mechanical Person', 'Artificial Intelligence', 'Mascot'],
    ['Downloadable','Stock','3d', 'Digital', 'Robotics'],
    ['Clipart','Illustration','Render', 'Image', 'Graphic'],
]) 

used = []

i = 0

def make_sentence(m, used):
    sentence = []
    i = 0
    while i <= 3:
        word = m[i,random.randrange(0,4)]
        sentence.append(word)
        i = i+1
    return ' '.join(sentence)

def is_used(sentence, used):
    if sentence not in used:
        return False
    else: 
        return True

sentences = []      
i = 0
while i <= 1000:
    sentence = make_sentence(m, used)
    if(is_used(sentence, used)):
        continue
    else:       
        sentences.append(sentence)
        print str(i) + ' ' +sentence
        used.append(sentence)
        i = i+1

Using randint instead of randrange, I get up to 624 combinations (instantly) then it hangs in an infinite loop, unable to create more combos.

I guess the question is, is there a more appropriate way of determining all possible combinations of a matrix?

http://stackoverflow.com/questions/1208118/using-numpy-to-build-an-array-of-all-combinations-of-two-arrays ? — Henrik Andersson, Oct 31 '14 at 05:34

score 3 · Accepted Answer · answered Oct 31 '14 at 05:58

You can make use of itertools to get the all possible combinations of matrix. I given one example to show how itertools will work.

 import itertools
 mx = [
  ['Robot','Cyborg','Andoid', 'Bot', 'Droid'],
  ['Character','Concept','Mechanical Person', 'Artificial Intelligence', 'Mascot'],
  ['Downloadable','Stock','3d', 'Digital', 'Robotics'],
  ['Clipart','Illustration','Render', 'Image', 'Graphic'],
  ]
for combination in itertools.product(*mx):
     print combination

score 0 · Answer 2 · answered Oct 31 '14 at 06:09

Your code can make use of recursion. Without itertools, here is one strategy:

def make_sentences(m, choices = []):
    output = []
    if len(choices) == 4:
         sentence = ""
         i = 0
         #Go through the four rows of the matrix 
         #and choose words for the sentence
         for j in choices:
             sentence += " " + m[i][j]
             i += 1
    return [sentence] #must be returned as a list
    for i in range(0,4):
         output += make_sentences(m, choices+[i])
    return output #this could be changed to a yield statement

This is quite different from your original function.

The choices list keeps track of the index of the column for each ROW in m that has been selected. When the recursive method finds that choices four rows have been selected, it outputs a list with just ONE sentence.

Where the method finds that the choices list doesn't have four elements, it recursively calls itself for FOUR new choices lists. The results of these recursive calls are added to the output list.

Get all possible combinations of rows in a matrix

2 Answers2