All possible lists from ups and downs between elements in python list

Question

I have a function that compares sequential elements from a python list and returns 1 and -1:

>>> up_down([0, 2, 1, 3])
[1, -1, 1]

I need a function to return all possible lists from a '-1, 1' list using the function up_down.

>>> possible_lists([1, -1])
[[0, 2, 1], [1, 0, 2]]

I'd like to know if I can write these functions in a better way. My code is below:

import itertools
def comparison(a, b):
 if b > a:
 return 1
 if b < a:
 return -1
 else:
 return 0
def up_down(data, n=1):
 return [comparison(data[pos], data[pos + n]) for pos, value in enumerate(data[:-n])]
def possible_lists(data, n=1):
 size = len(data) + n
 all_lists = itertools.permutations(range(size), size)
 return [list(el) for el in all_lists if up_down(el, n) == data]

Answer 1

Your comparison function is the same as the builtin cmp function.

Your filtering technique to find the matching lists may be not the most efficient. Permutations will generate a lot of lists which fail the test. On the other hand, itertools is written in C, which means it'll probably be faster for small data sets.

• msampaio: Thanks, @Winston. What alternative do I have if I need to use data sets between 10 and 20 elements?
• Winston Ewert: @MarcosdaSilvaSampaio, start with a recursive algorithm that calculate what permutations does. Then abandon any list as soon as its not a valid prefix of your desired list.

Answer 2

For up_down, the algorithm is good, but can be implemented more simply: Use cmp built-in, thx to @Winston Use itertools built-ins to eliminate redundant index math, indexed access("[]") , and list copying ("[:]").

# compare each element with its nth successor.
def up_down(data, n=1):
 # iterate in parallel over data and its n-shifted slice
 return imap(cmp, data, itertools.islice(data, n, None))]

For possible_lists, you could do much better than generating the entire permutation set. Instead, consider an approach that generates an initial list that provably matches the up_down data and then applies a series of mutations to that list, generating other lists that preserve its up_down profile until all such lists have been provably generated.

In an optimal solution,

• the initial list would be cheap to generate

• the initial list would be "minimal" according to some metric.

• the mutator function would generate the next minimal list (i.e. "next most minimal?" "next least?").

In a less-than-optimal solution,

• the initial list would at least be cheaper to generate than it would be to discover by the OP's "permute and test" method

• the "minimality" idea could be abandoned

• the mutator function could generate a set of successor lists, test them against the set of lists already seen, and mutate any one of them that isn't in a set of those already mutated.

I believe that an optimal solution is worth pursuing, especially since it might allow possible_lists to export a "generator" interface that produced each matching list sequentially with a minimal memory footprint.

I also believe that a good solution for n> 1 is likely to be found by somehow post-processing all combinations of the n independent solutions for the lists of every nth element of the original.