Как я могу использовать разные типы перестановок в Python3?

Question

Нормальный вид перестановки:

'ABC' 
    ↓ 
'ACB' 
'BAC' 
'BCA' 
'CAB' 
'CBA' 

Но что, если я хочу, чтобы это сделать:

'ABC' 
    ↓ 
'AA' 
'AB' 
'AC' 
'BA' 
'BB' 
'BC' 
'CA' 
'CB' 
'CC' 

Что это называется, и насколько эффективно это было бы с массивами с сотнями элементов ?

Answer 1

Ваша терминология немного запутанна: то, что у вас есть, не является перестановкой ваших персонажей, а скорее сочетанием всех возможных персонажей с любым возможным характером: декартовым произведением.

Вы можете использовать itertools.product для создания этих комбинаций, но обратите внимание, что это возвращает итератор, а не контейнер. Так что если вам нужны все комбинации в списке, вам нужно построить list явно:

from itertools import product 
mystr = 'ABC' 
prodlen = 2 
products = list(product(mystr,repeat=prodlen)) 

Или, если вы только в течение этих циклов значений:

for char1,char2 in product(mystr,repeat=prodlen): 
    # do something with your characters 
    ... 

Или, если вы хотите генерировать строки 2 длины, вы можете сделать это в списке понимание:

allpairs = [''.join(pairs) for pairs in products] 
# ['AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC'] 

Answer 2

Как говорит Andras Deak, используя itertools product:

import itertools 

for i, j in itertools.product('ABC', repeat=2): 
    print(i + j) 

Answer 3

Ничто против itertools, но если вы хотите немного понять, как вручную генерировать перестановки строк, применяя модульную арифметику к инкрементному порядковому номеру. Должен работать со строкой любой длины и любого значения n где n <= len(s)

Число перестановок Вырабатываемые len(s) ** n

Например, просто позвоните printPermutations("abc", 2)

def printPermutations(s, n) : 
    if (not s) or (n < 1): 
     return 
    maxpermutations = len(s) ** n 
    for p in range(maxpermutations): 
     perm = getSpecificPermutation(s, n, p) 
     print(perm) 

def getSpecificPermutation(s, n, p): 
    # s is the source string 
    # n is the number of characters to extract 
    # p is the permutation sequence number 
    result = '' 
    for j in range(n): 
     result = s[p % len(s)] + result 
     p = p // len(s) 
    return result 

Answer 4

Вы хотите использовать itertools решение. Но я знаю, как это называется ...

Большинство людей называют это подсчетом. Ты обманываешься, но я думаю, что это просто счет в базе len(set), где set - ваш ввод set (Я предполагаю, что это действительно набор, не повторяющиеся элементы). Представьте себе, в вашем примере A -> 0, B->1, C->2. Вы также запрашиваете элементы с определенным количеством максимальных цифр.Позвольте мне показать вам:

def numberToBase(n, b): 
    if n == 0: 
     return [0] 
    digits = [] 
    while n: 
     digits.append(int(n % b)) 
     n /= b 
    return digits[::-1] 

def count_me(set, max_digits=2): 
    # Just count! From 0 to len(set) ** max_digits to be precise 
    numbers = [i for i in range(len(set) ** max_digits)] 

    # Convert to base len(set) 
    lists_of_digits_in_base_b = [numberToBase(i, len(set)) for i in numbers] 

    # Add 0s to the front (making each list of digits max_digit - 1 in length) 
    prepended_with_zeros = [] 
    for li in lists_of_digits_in_base_b: 
     prepended_with_zeros.append([0]*(max_digits - len(li)) + li) 

    # Map each digit to an item in our set 
    m = {index: item for index, item in enumerate(set)} 
    temp = map(lambda x: [m[digit] for digit in x], prepended_with_zeros) 

    # Convert to strings 
    temp2 = map(lambda x: [str(i) for i in x], prepended_with_zeros) 

    # Concatenate each item 
    concat_strings = map(lambda a: reduce(lambda x, y: x + y, a, ""), temp) 

    return concat_strings 

Вот некоторые выходы:

print count_me("ABC", 2) 

выходы:

['AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC'] 

и

print count_me("ABCD", 2) 

выходы:

['AA', 'AB', 'AC', 'AD', 'BA', 'BB', 'BC', 'BD', 'CA', 'CB', 'CC', 'CD', 'DA', 'DB', 'DC', 'DD'] 

и

print count_me("ABCD", 3) 

выходов (один большой):

['AAA', 'AAB', 'AAC', 'AAD', 'ABA', 'ABB', 'ABC', 'ABD', 'ACA', 'ACB', 'ACC', 'ACD', 'ADA', 'ADB', 'ADC', 'ADD', 'BAA', 'BAB', 'BAC', 'BAD', 'BBA', 'BBB', 'BBC', 'BBD', 'BCA', 'BCB', 'BCC', 'BCD', 'BDA', 'BDB', 'BDC', 'BDD', 'CAA', 'CAB', 'CAC', 'CAD', 'CBA', 'CBB', 'CBC', 'CBD', 'CCA', 'CCB', 'CCC', 'CCD', 'CDA', 'CDB', 'CDC', 'CDD', 'DAA', 'DAB', 'DAC', 'DAD', 'DBA', 'DBB', 'DBC', 'DBD', 'DCA', 'DCB', 'DCC', 'DCD', 'DDA', 'DDB', 'DDC', 'DDD'] 

P.S. numberToBase любезно предоставлено this post