Циклический цикл

#python #алгоритм

Язык не важен, поясню на примере языка питон:

myarray=['a', 'b', 'c']
number=3
def myfunc(myarray, number): #при number = 3
  newarray=[]
  for s1 in myarray
    for s2 in myarray
      for s3 in myarray
        newarray.append(s1+s2+s3)
  return newarray


должен возвратить: aaa, aab, aac, aba, abb, abc, итд, Т.е. если number = 4, то все
четырехзначные, что можно составить, если 5, то пятизначные и тд.

Как это сделать?
    

Ответы

Ответ 1

from itertools import product

chars = 'abc'

print(list(product(chars, repeat=3)))

# [('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ...


Выходные данные уже преобразуй во что нужно.

Вот псевдо-код реализации product() из документации:

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)


Ответ 2

Простой алгоритм генерации сочетаний с повторениями: представим наше множество как
набор цифр. Тогда все возможные сочетания с повторениями - это просто все возможные
числа с заданной разрядностью на заданном наборе цифр.
Самый простой способ получить все возможные числа - выбрать некоторый "ноль" и постепенно
его увеличивать.

Посмотрим как мы это делаем в арифметике. Допустим у нас есть цифры A, B и C и максимальная
разрядность равна 2. За "ноль" примем первое число, т.е. A (а с учетом разрядности: AA)

Тогда, увеличивая это число на 1, мы сначала увеличиваем первый разряд на 1 (т.е.
берем следующую возможную цифру), а если у нас возникает переполнение (т.е. больше
нет доступных цифр), значит сбрасываем текущий разряд на "ноль" и увеличиваем следующий
разряд числа на 1 и т.д.

Немного примеров:

ноль - AA
AA + 1 = AB (т.к. B - следующая цифра после A)
AB + 1 = AC (т.к. C - следующая цифра после B)
AC + 1 = BA (т.к. после C нет доступных цифр, то обнуляем первый разряд и увеличиваем
на 1 второй разряд)
и т.д.


Т.е. алгоритм генерации наших сочетаний простой:


Генерируем первое число необходимой разрядности (ноль)
Увеличиваем число, полученное на предыдущем шаге на 1
Повторяем пункт 2 до тех пор, пока в последнем разряде не получим переполнение (т.е.
следующее возможное число будет уже с разрядностью большей заданной)


Алгоритм увеличения числа на 1 тоже простой:


На входе у нас возможные цифры числа, само число и разряд, который мы собираемся
увеличивать
Увеличиваем текущий разряд на 1
Если возникло переполнение - обнуляем текущий разряд и повторяем алгоритм для следующего
разряда
Если возникло переполнение, но текущий разряд - последний в выбранной разрядности
- мы получили максимальное число в выбранной разрядности


В коде на python это выглядит как-то так:

def increase_number(digits, number, increased_index = 0):
    number = list(number)
    total_digits_count = len(digits)
    number_digits_count = len(number)

    # было переполнение в последнем доступном разряде
    if increased_index >= number_digits_count:
        return False

    current_digit = number[increased_index]
    current_digit_index = digits.index(current_digit)

    # если в текущем разряде переполнение - увеличиваем на 1 следующий разряд
    if current_digit_index + 1 >= total_digits_count:
        number[increased_index] = digits[0]
        return increase_number(digits, number, increased_index + 1)

    # в текущий разряд пишем следующую по списку цифру
    number[increased_index] = digits[current_digit_index + 1]
    return number

def product(digits, repeat=3):
    all_products = []
    current_number = [digits[0]] * repeat
    while True:
        yield current_number
        current_number = increase_number(digits, current_number)

        # было переполнение последнего разряда, больше чисел нет
        if current_number == False:
            break

myarray=['5', 'O', 'S']
result = product(myarray, 2)
for number in result:
    print (''.join(number))

# Вывод:
# 55
# O5
# S5
# 5O
# OO
# SO
# 5S
# OS
# SS


Не стал заморачиваться, поэтому здесь числа немного перевернуты. Т.е. вместо числа
0123 на выводе будет 3210, но на результат это никоим образом не влияет


Ответ 3

Рекурсивный вызов

def myfunc(myarray, number=3):
    result=[]
    if number > 1:
        for s1 in myarray:
            tmp = myfunc(myarray, number - 1)
            for item in tmp:
                result.append(s1+item)
    else:
        result = myarray
    return result


Ответ 4

Только что решал аналогичную проблему в теме про кластеризацию (процедура combinations),
генерировал сочетания без повторений.

Адаптация труда не составляет (PHP):

function combi_all($chars, $num){
    $combi = [""];  
    for($n = 0; $n < $num; $n++){
        $combi_old = $combi;
        $combi = [];
        foreach($combi_old as $item){
            for($m = 0; $m < $num; $m++){
                $combi[] = $item.$chars[$m];
            }
        }
    }
    return $combi;
}

$combi = combi_all(["a","b","c","d"],3);
var_dump($combi);


Результаты:


array (size=27)
  0 => string 'aaa' (length=3)
  1 => string 'aab' (length=3)
  2 => string 'aac' (length=3)
  3 => string 'aba' (length=3)
  4 => string 'abb' (length=3)
  5 => string 'abc' (length=3)
  6 => string 'aca' (length=3)
  7 => string 'acb' (length=3)
  8 => string 'acc' (length=3)
  9 => string 'baa' (length=3)
  10 => string 'bab' (length=3)
  11 => string 'bac' (length=3)
  12 => string 'bba' (length=3)
  13 => string 'bbb' (length=3)
  14 => string 'bbc' (length=3)
  15 => string 'bca' (length=3)
  16 => string 'bcb' (length=3)
  17 => string 'bcc' (length=3)
  18 => string 'caa' (length=3)
  19 => string 'cab' (length=3)
  20 => string 'cac' (length=3)
  21 => string 'cba' (length=3)
  22 => string 'cbb' (length=3)
  23 => string 'cbc' (length=3)
  24 => string 'cca' (length=3)
  25 => string 'ccb' (length=3)
  26 => string 'ccc' (length=3)


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