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

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]


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.

• Thanks, @Winston. What alternative do I have if I need to use data sets between 10 and 20 elements? – msampaio Feb 20 '12 at 21:05
• @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. – Winston Ewert Feb 21 '12 at 4:01

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.