maxpath.py

#!/usr/bin/env python
# Author: Cian Johnston <[email protected]>

import argparse
import itertools


def distance(s1, s2):
    out = abs(len(s1) - len(s2))
    for c1, c2 in zip(s1, s2):
        if c1 != c2:
            out += 1
    return out


def valid_children(path, combinations):
    head = path[-1]
    tail = path[:-1]
    cands = [c for c in combinations if distance(c, head) == 1 and c not in tail]
    return cands


def validate(path, combinations, should_be_circular=False):
    is_circular = distance(path[0], path[-1]) == 1
    has_all_elements = set(path) == set(combinations)  # too slow?
    if should_be_circular:
        return is_circular and has_all_elements
    return has_all_elements


def main():
    help_msg = """Computes possible combinations of length n from a list of tokens where:
    only one token changes at a time in a comabination and no combination is repeated"""
    ap = argparse.ArgumentParser(description=help_msg)
    ap.add_argument("tokens")
    ap.add_argument("length", type=int)
    ap.add_argument("--start", type=str, nargs="+")
    ap.add_argument("--circular", action="store_true", default=False)
    args = ap.parse_args()

    # if you don't care about ordering use itertools.permutations instead.
    combinations = [''.join(t) for t in itertools.combinations(args.tokens, args.length)]

    print("Possible combinations: %d" % len(combinations))

    if args.start:
        paths = [args.start]
    else:
        paths = [[combinations[0]]]

    while True:
        try:
            current_path = paths.pop(0)
        except IndexError:
            print("No more possible paths.")
            break
        for child in valid_children(current_path, combinations):
            new_path = current_path + [child]
            if validate(new_path, combinations, args.circular):
                print("Path found:"),
                print(" -> ".join(new_path))
                if raw_input("Another? [y/n] ").lower() == 'n':
                    raise SystemExit 
            else:
                # paths.append(np)  # breadth-first search takes forever
                paths.insert(0, new_path)


if __name__ == "__main__":
    main()