Перестановки из серии цветных шариков, без 2 одинакового цвета рядом друг с другом?

Question

Вводом является строка (a, b, c, d, ...).В этой строке a означает шары одного цвета, b означает шары другого цвета и т. Д. Таким образом, (2, 1, 3) означает 2 красных шара, 1 синий шар и 3 желтых шара.

Выход 1 - это количество возможных перестановок, без двух шариков одного цвета рядом друг с другом.

Выход 2 - список всех этих перестановок.

Например:

Вход: (2, 1, 3)

Выход 1: 10 перестановок

Выход 2: 131323, 132313, 231313, 312313, 313123 и т. Д.

Итак, мой главный вопрос: как мне отфильтровать перестановки, в которых 2 или более шариков одного цвета находятся рядом друг с другом в программе Python?

Answer 1

Предполагая, что output2 является массивом ваших строк перестановок, вы можете фильтровать массив, отбрасывая перестановки, имеющие (как минимум) два последовательных цветовых кода:

import re
output2 = filter(lambda perm: not re.search(r"(\d)\1", perm), output2)

Объясненное регулярное выражение: \d соответствует любому числу.Окружающие скобки отмечают «подходящую группу».\1 разрешается в первую подходящую группу.Таким образом, в комбинации (\d)\1 совпадает с любыми двумя последовательными одинаковыми числами.

Если output2 не массив, а список через запятую в виде строки, вы можете разделить его следующим образом, чтобыполучить массив:

output2 = output2.split(', ')

Answer 2

Это немного запутанно, и, возможно, есть более эффективная версия, но это должно сработать:

output2=['12234','22341','1234','12344']

permut=[]
for num in b: #For every element in the list output2
    for n,i in enumerate(num): #For every index and number inside every element of the list
        if n>0: #This is only for the next line to work on the first iteration
            if num[n]==num[n-1]: #If a number is the same than the previous number
                permut.append(num) #append into a new list the whole permutation number
                break #Go to the next loop
            else:
                continue
        else:
            continue

Answer 3

Определенно не самый аккуратный способ ведения дел, но с использованием ответа на этот вопрос:

https://stackoverflow.com/a/36343769/9742036

Как проверять наличие равных соседей в списке, это должно сделатьхитрость.

Сначала мы создаем список, представляющий вашу комбинацию шаров, просматриваем все их комбинации и затем отфильтровываем те, которые недопустимы.

from itertools import permutations
from operator import eq

input = (2, 1, 3)

# Produce a list to represent the objects to order. (2,1,3) -> [0, 0, 1, 2, 2, 2]
list_of_items = []
current_item = 1
for value in input:
    for number in range(value):
        list_of_items.append(current_item)

    current_item += 1



count_of_valid_permutations = 0
set_of_valid_permutations = set()

# Generate all permutations of our list
for permutation in permutations(list_of_items):
    # Permutations treat each ball as unique, even if the same colour, so check we're not over counting.
    if permutation not in set_of_valid_permutations:

        # Use the eq operator and map it to the permutation to see if any neighbours are equal.
        hasEqualNeigbours = any(map(eq, permutation, permutation[1:]))
        # If not, then this is a valid permutation.
        if not hasEqualNeigbours:
            # Record the permutation as seen.
            set_of_valid_permutations.add(permutation)
            count_of_valid_permutations += 1


print(count_of_valid_permutations)
print(set_of_valid_permutations)

Answer 4

Приведенный ниже код решит вашу проблему:

import numpy as np
num = 221333 ## Any random permutation
lst = list(map(int, str(num)))
req_array = np.diff(lst)
if 0 in req_array:
    print ("Yes")

Приведенный выше код работает в следующей логике:

1. Повторяйте список перестановок один за другим.Код выше для 1 такого элемента в этом списке
2. Преобразование number в array
3. Субъективные последовательные элементы
4. Если массив равен нулю, то существует одинкомбинация, в которой 2 шарика одного цвета