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
        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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.