Recursive permutations of size k with no same elements next to each other-CodePudding

This is my first question, so please pardon my formatting. I am basically trying to create permutations with repetitions of size k with no repeating elements next to each other. So, i have a list like 1,2,3,4 and a k value. For example, by taking 1,2,3,4 and k=4,

1,3,2,3 would be a valid output, but 1,3,3,2 would not. I can do basic permutations recursively, but I’ve been struggling with this for a while. I don’t want to import any libraries as I think it could be done without it. Any help would be appreciated!

CodePudding user response：

I know, you didn't want to use a library, but you need to have some sort of randomness:

from random import sample 
k = 4
l = [i for i in range(k)]
sample(l, k)

and this would be recursive:

from random import randint

def recursvie_sample(l, k):
    if k == 1:
        return l
    else:
        return [l.pop(randint(0, k - 1))]   recursvie_sample(l, k - 1)

k = 4
l = [i for i in range(k)]
recursvie_sample(l.copy(), k)

Note: copying list l as input value for the recursive_sample keepsl unaltered through the function call, and you could still use it afterwards...

CodePudding user response：

I believe this does what you want:

import random

options = [2,4,6,8]
k = 15

def add_element(current_list, k, options):
    if len(current_list)<k:
        prev_element = None if len(current_list)==0 else current_list[-1]
        new_element  = random.choice(list(set(options)-{prev_element}))
        return add_element(current_list   [new_element], k, options)
    else:
        return current_list

add_element([],k,options)

Output:

[8, 6, 2, 4, 8, 6, 2, 8, 4, 8, 6, 8, 2, 8, 6]