efficient algorithm for hops along a chain

Question

I'm mentally stuck at the following problem: I need an efficient algorithm to create possible hops along a chain.

The "real life" screnario is the following: You have a route with n stations. There can be different patterns of stops on this route, e.g. on a route where n=4, there are stops at station 1, 3 and 4.

I think this is nothing for the classical routing algorithms like Dijkstra's or A*, but I am very positive this is easy to solve ... but what is the most efficient way?

What would be an efficient algorithm to create these sets? The generated rows would look like the following:

var sets = [
    stationCount2: [
        [0, 1]
    ],

    stationCount3: [
        [0, 2],
        [0, 1, 2]
    ],

    stationCount4: [
        [0, 3],
        [0, 1, 3],
        [0, 2, 3],
        [0, 1, 2, 3]
    ],

    stationCount5: [
        [0, 4],
        [0, 1, 4],
        [0, 2, 4],
        [0, 3, 4],
        [0, 1, 2, 4],
        [0, 1, 3, 4],
        [0, 2, 3, 4],
        [0, 1, 2, 3, 4]
    ]
];

Or is there a "known" algorithm for that?

http://stackoverflow.com/questions/9960908/permutations-in-javascript, http://codereview.stackexchange.com/questions/7001/better-way-to-generate-all-combinations — Andreas, Apr 17 '13 at 10:04
Thanks, the second link contained some useful hints at my problem, I'll be able to go from there. — lxg, Apr 18 '13 at 09:11

score 0 · Answer 1 · answered Apr 17 '13 at 12:52

0

There is a package math_combinatoric: http://pear.php.net/package/Math_Combinatorics

answered Apr 17 '13 at 12:52

Micromega

12,486
7
35
72

Thanks, I'll have a look at their implementations. – lxg Apr 18 '13 at 09:12

efficient algorithm for hops along a chain

1 Answers1