Generate all possible sequences of N elements with sequential rules

Question

I have a function get_appendable_values(sequence) that takes a sequence (even empty) and returns a list of all the values appendable (as a last element) to that sequence. I need to generate all the possible sequences of 4 elements, with respect to the rules defined in this function and starting with an empty sequence.

Example :

Let's say the implementation of get_appendable_values is :

def get_appendable_values(sequence):
    '''Dummy rules'''
    if len(sequence) == 2:
        return [4, 12]
    if sequence[-1] == 4:
        return [7]
    return [0, 9]

Expected output :

[[0, 0, 4, 7],
[0, 0, 12, 0],
[0, 0, 12, 9],
[0, 9, 4, 7],
[0, 9, 12, 0],
[0, 9, 12, 9],
[9, 0, 4, 7],
[9, 0, 12, 0],
[9, 0, 12, 9],
[9, 9, 4, 7],
[9, 9, 12, 0],
[9, 9, 12, 9]]

I have the feeling that recursion is the key, but I could not figure it out.

You need to provide your code in order to get help, otherwise it's impossible — imburningbabe, Oct 03 '22 at 12:08
I unfortunately did not succeed to write any minimal (even wrong) code as I'm stuck with the algorithm. Is the description of the problem unclear ? — Betcha, Oct 03 '22 at 12:13
Yeah :). Try to write down a generic input and what do you expect as output — imburningbabe, Oct 03 '22 at 12:21
I have closed the question as a duplicate matching what is the currently described task. Note that if you feel this does not solve your problem, please [edit] your question to clarify what exactly the requirements are; see also [ask]. Note that right now *we don't know* "the rules defined in this function", so "generate all the possible sequences" of those means treating the function as a black-box and creating the permutations of its output. — MisterMiyagi, Oct 03 '22 at 12:49
I did not give the implementation of `get_appendable_values` on purpose, because I want it to be generic... I'll edit my initial post to give an example, but that's definitly not about permutations. — Betcha, Oct 03 '22 at 12:52
Is there *anything* known about `get_appendable_values`? The example looks at specific values inside the `sequence`, so one could conceivably have to try *all possible Python values* to probe for all possible return values. Even if Python had finite values that would be computationally infeasible, but Python has *several* unbounded types (prominently `int`, but also every container for example) which means this is impossible in the generic case. — MisterMiyagi, Oct 03 '22 at 13:19
No, we do not know anything about `get_appendable_values`. Except the fact that it always returns a finite set of values. We can consider that we do not have its implementation. And I need the algorithm to be agnostic to this function. I do not understand your point about computation feasibility though. — Betcha, Oct 03 '22 at 13:26
If you're trying to solve a [constraint satisfaction problem](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem) you should know that A) Python isn't really the best for this category of problems and B) you'll need to be much more specific in your question. — 0x263A, Oct 03 '22 at 13:34

score 6 · Accepted Answer · answered Oct 03 '22 at 13:41

Yes, recursion is the key. To generate a sequence of size 4, you first generate all sequences of size 3, and add all possible endings to them. Likewise, to generate a sequence of size 3, you need all sequences of size 2... and so forth down to size 0.

def get_appendable_values(sequence):
    '''Dummy rules'''
    if len(sequence) == 2:
        return [4, 12]
    #need a len check here to avoid IndexError when `sequence` is empty
    if len(sequence) > 0 and sequence[-1] == 4:
        return [7]
    return [0, 9]

def generate_sequences(size):
    if size == 0:
        yield []
    else:
        for left_part in generate_sequences(size-1):
            for right_part in get_appendable_values(left_part):
                yield left_part + [right_part]

for seq in generate_sequences(4):
    print(seq)

Result:

[0, 0, 4, 7]
[0, 0, 12, 0]
[0, 0, 12, 9]
[0, 9, 4, 7]
[0, 9, 12, 0]
[0, 9, 12, 9]
[9, 0, 4, 7]
[9, 0, 12, 0]
[9, 0, 12, 9]
[9, 9, 4, 7]
[9, 9, 12, 0]
[9, 9, 12, 9]

How would you modify this function to handle the fact that `get_appendable_values` can return `[]` (i.e. no value can be appendable), and thus we should early stop the exploration of this branch because it will not give a 4 elements sequence ? Is there an easy backtracking-ish way to do so ? — Betcha, Oct 09 '22 at 15:27

Adrian Usler · Answer 2 · 2022-10-03T12:31:01.293

-1

I'm not sure if I understand your problem correctly. Do you want to get a list of the possible permutations of length 4, drawn from the sequence?

In that case, the itertools package might come in handy (see How do I generate all permutations of a list?):

import itertools

a = [2, 4, 6, 8, 10]

permutations_object = itertools.permutations(a, 4)

print(list( permutations_object ))

This outputs a list of tuples which are the permutations:

[(2, 4, 6, 8), (2, 4, 6, 10), (2, 4, 8, 6), (2, 4, 8, 10), ...]

edited Oct 03 '22 at 12:31

answered Oct 03 '22 at 12:29

Adrian Usler

81
7

Thank you for replying but no I did not talk about permutations. I want to generate all the sequences of a certain length that could be generated with respect to the values that get_appendable_values give – Betcha Oct 03 '22 at 12:32
Could you specify what you meant? – Adrian Usler Oct 03 '22 at 12:34
Sorry, but I still don't see how this is not about permutations. Could you help me out by saying which output you would expect in an example where the input is the list [1, 2, 3] and you want to generate sequences of length 2? – Adrian Usler Oct 03 '22 at 12:39
Only certain values can be appendable to a certain sequence (those values are defined by the "get_appendable_values(sequence)" (order matter!) Thus, I can not give you the expected ouput for [1, 2, 3] as it depends on this function. – Betcha Oct 03 '22 at 12:43
Ok, I get it a little better now. I suppose you could work this extra criterion into the general permutation algorithm that Aidan Wansbrough posted...? – Adrian Usler Oct 03 '22 at 12:52

score -1 · Answer 3 · answered Oct 03 '22 at 12:33

Here's a solution which works using recursion, although as Adrian Usler suggests, using the itertools library probably works better. I think the following code works:

def gen_all_sequences(sequence):
    # Recursive base case:
    if len(sequence) <= 1:
        return [sequence] # Only one possible sequence of length 1
    
    # Recursive general case:
    all_sequences = []
    for i, elem in enumerate(sequence):
        # Construct and append all possible sequences beginning with elem
        remaining_elements = sequence[:i]+sequence[i+1:] 
        all_sequences += [[elem]+seq for seq in gen_all_sequences(remaining_elements )]
    return all_sequences

print(gen_all_sequences(["a","b","c","d"]))
# Will return all arrangements (permutations) of "a", "b", "c" and "d", e.g. abcd, abdc, acbd, acdb etc.

Thank you for your reply but that's really not about permutations. I've edited my initial post to add an example. — Betcha, Oct 03 '22 at 13:04

Generate all possible sequences of N elements with sequential rules

3 Answers3