Hướng dẫn permutation with repeated elements python - hoán vị với các phần tử lặp lại python

from more_itertools import distinct_permutations

x = [p for p in distinct_permutations(['M','I','S', 'S', 'I'])]

for item in x:
    
  print(item)

Output:

('I', 'S', 'S', 'I', 'M')
('S', 'I', 'S', 'I', 'M')
('S', 'S', 'I', 'I', 'M')
('I', 'S', 'I', 'S', 'M')
('S', 'I', 'I', 'S', 'M')
('I', 'I', 'S', 'S', 'M')
('I', 'S', 'I', 'M', 'S')
('S', 'I', 'I', 'M', 'S')
('I', 'I', 'S', 'M', 'S')
('I', 'I', 'M', 'S', 'S')
('I', 'S', 'S', 'M', 'I')
('S', 'I', 'S', 'M', 'I')
('S', 'S', 'I', 'M', 'I')
('S', 'S', 'M', 'I', 'I')
('I', 'S', 'M', 'S', 'I')
('S', 'I', 'M', 'S', 'I')
('S', 'M', 'I', 'S', 'I')
('S', 'M', 'S', 'I', 'I')
('I', 'M', 'S', 'S', 'I')
('M', 'I', 'S', 'S', 'I')
('M', 'S', 'I', 'S', 'I')
('M', 'S', 'S', 'I', 'I')
('I', 'S', 'M', 'I', 'S')
('S', 'I', 'M', 'I', 'S')
('S', 'M', 'I', 'I', 'S')
('I', 'M', 'S', 'I', 'S')
('M', 'I', 'S', 'I', 'S')
('M', 'S', 'I', 'I', 'S')
('I', 'M', 'I', 'S', 'S')
('M', 'I', 'I', 'S', 'S')

Tạo hoán vị của các phần tử

('I', 'S', 'S', 'I', 'M')
('S', 'I', 'S', 'I', 'M')
('S', 'S', 'I', 'I', 'M')
('I', 'S', 'I', 'S', 'M')
('S', 'I', 'I', 'S', 'M')
('I', 'I', 'S', 'S', 'M')
('I', 'S', 'I', 'M', 'S')
('S', 'I', 'I', 'M', 'S')
('I', 'I', 'S', 'M', 'S')
('I', 'I', 'M', 'S', 'S')
('I', 'S', 'S', 'M', 'I')
('S', 'I', 'S', 'M', 'I')
('S', 'S', 'I', 'M', 'I')
('S', 'S', 'M', 'I', 'I')
('I', 'S', 'M', 'S', 'I')
('S', 'I', 'M', 'S', 'I')
('S', 'M', 'I', 'S', 'I')
('S', 'M', 'S', 'I', 'I')
('I', 'M', 'S', 'S', 'I')
('M', 'I', 'S', 'S', 'I')
('M', 'S', 'I', 'S', 'I')
('M', 'S', 'S', 'I', 'I')
('I', 'S', 'M', 'I', 'S')
('S', 'I', 'M', 'I', 'S')
('S', 'M', 'I', 'I', 'S')
('I', 'M', 'S', 'I', 'S')
('M', 'I', 'S', 'I', 'S')
('M', 'S', 'I', 'I', 'S')
('I', 'M', 'I', 'S', 'S')
('M', 'I', 'I', 'S', 'S')
0 (bao gồm cả các yếu tố lặp lại/trùng lặp)

ab = aa, bb, ab, ba
abc = aaa, aab, abc ...

Số lượng kết hợp phải là

('I', 'S', 'S', 'I', 'M')
('S', 'I', 'S', 'I', 'M')
('S', 'S', 'I', 'I', 'M')
('I', 'S', 'I', 'S', 'M')
('S', 'I', 'I', 'S', 'M')
('I', 'I', 'S', 'S', 'M')
('I', 'S', 'I', 'M', 'S')
('S', 'I', 'I', 'M', 'S')
('I', 'I', 'S', 'M', 'S')
('I', 'I', 'M', 'S', 'S')
('I', 'S', 'S', 'M', 'I')
('S', 'I', 'S', 'M', 'I')
('S', 'S', 'I', 'M', 'I')
('S', 'S', 'M', 'I', 'I')
('I', 'S', 'M', 'S', 'I')
('S', 'I', 'M', 'S', 'I')
('S', 'M', 'I', 'S', 'I')
('S', 'M', 'S', 'I', 'I')
('I', 'M', 'S', 'S', 'I')
('M', 'I', 'S', 'S', 'I')
('M', 'S', 'I', 'S', 'I')
('M', 'S', 'S', 'I', 'I')
('I', 'S', 'M', 'I', 'S')
('S', 'I', 'M', 'I', 'S')
('S', 'M', 'I', 'I', 'S')
('I', 'M', 'S', 'I', 'S')
('M', 'I', 'S', 'I', 'S')
('M', 'S', 'I', 'I', 'S')
('I', 'M', 'I', 'S', 'S')
('M', 'I', 'I', 'S', 'S')
1 (n = số phần tử, k = chiều dài kết hợp). Đối với trường hợp này,
('I', 'S', 'S', 'I', 'M')
('S', 'I', 'S', 'I', 'M')
('S', 'S', 'I', 'I', 'M')
('I', 'S', 'I', 'S', 'M')
('S', 'I', 'I', 'S', 'M')
('I', 'I', 'S', 'S', 'M')
('I', 'S', 'I', 'M', 'S')
('S', 'I', 'I', 'M', 'S')
('I', 'I', 'S', 'M', 'S')
('I', 'I', 'M', 'S', 'S')
('I', 'S', 'S', 'M', 'I')
('S', 'I', 'S', 'M', 'I')
('S', 'S', 'I', 'M', 'I')
('S', 'S', 'M', 'I', 'I')
('I', 'S', 'M', 'S', 'I')
('S', 'I', 'M', 'S', 'I')
('S', 'M', 'I', 'S', 'I')
('S', 'M', 'S', 'I', 'I')
('I', 'M', 'S', 'S', 'I')
('M', 'I', 'S', 'S', 'I')
('M', 'S', 'I', 'S', 'I')
('M', 'S', 'S', 'I', 'I')
('I', 'S', 'M', 'I', 'S')
('S', 'I', 'M', 'I', 'S')
('S', 'M', 'I', 'I', 'S')
('I', 'M', 'S', 'I', 'S')
('M', 'I', 'S', 'I', 'S')
('M', 'S', 'I', 'I', 'S')
('I', 'M', 'I', 'S', 'S')
('M', 'I', 'I', 'S', 'S')
0 và
('I', 'S', 'S', 'I', 'M')
('S', 'I', 'S', 'I', 'M')
('S', 'S', 'I', 'I', 'M')
('I', 'S', 'I', 'S', 'M')
('S', 'I', 'I', 'S', 'M')
('I', 'I', 'S', 'S', 'M')
('I', 'S', 'I', 'M', 'S')
('S', 'I', 'I', 'M', 'S')
('I', 'I', 'S', 'M', 'S')
('I', 'I', 'M', 'S', 'S')
('I', 'S', 'S', 'M', 'I')
('S', 'I', 'S', 'M', 'I')
('S', 'S', 'I', 'M', 'I')
('S', 'S', 'M', 'I', 'I')
('I', 'S', 'M', 'S', 'I')
('S', 'I', 'M', 'S', 'I')
('S', 'M', 'I', 'S', 'I')
('S', 'M', 'S', 'I', 'I')
('I', 'M', 'S', 'S', 'I')
('M', 'I', 'S', 'S', 'I')
('M', 'S', 'I', 'S', 'I')
('M', 'S', 'S', 'I', 'I')
('I', 'S', 'M', 'I', 'S')
('S', 'I', 'M', 'I', 'S')
('S', 'M', 'I', 'I', 'S')
('I', 'M', 'S', 'I', 'S')
('M', 'I', 'S', 'I', 'S')
('M', 'S', 'I', 'I', 'S')
('I', 'M', 'I', 'S', 'S')
('M', 'I', 'I', 'S', 'S')
3 là giống nhau.

ab = 2^2 = 4
abc = 3^3 = 9

If we use `abc`(n=3) to generate permutations of length 1 (k=1)
P(abc, 1) = a, b, c = 3^1 = 3 combinations

If we use `abc`(n=3) to generate permutations of length 2 (k=2)
P(abc, 2) = aa, bb, cc, ab, ac ... = 3^2 = 9 combinations

Lặp lại tuyến tính của tất cả các yếu tố khó có thể tạo ra tất cả các kết hợp, vì vậy một giải pháp đệ quy có nhiều khả năng.

Hãy tưởng tượng sơ đồ sau.

Hướng dẫn permutation with repeated elements python - hoán vị với các phần tử lặp lại python

Kết quả của p (a) được sử dụng để tạo p (ab). Chúng tôi bắt đầu với một tiền tố 1 ký tự, sau đó chúng tôi nhiều ký tự hơn để có tiền tố cho đến khi tất cả sự kết hợp được tạo đệ quy.

def _permutation_repeat(text, prefix, n, k):
    if k == 0: # base, len(prefix) == len(text)
        print(prefix)
        return

    for i in range(n):
        new_prefix = prefix + text[i] # a, aa, aaa, aab, aac ab, aba, abb, abc
        
        # print(new_prefix)
        _permutation_repeat(text, new_prefix, n, k-1)
    # print('---')


def permutation_repeat(text, k):
    _permutation_repeat(text, "", len(text), k)


permutation_repeat("abc", 3)

Sự kết hợp được tạo ra trong chuỗi sau.

a ->
  aa ->
    aaa
    aab
    aac
  ab ->
    aba
    abb
    abc
  ac ->
    aca
    acb
    acc
b ->
  ba ->
    baa
    bab
    bac
  ...
...  

Đầu ra

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

Hoán vị với lặp lại trong kết quả thực sự là sản phẩm của Cartesian.

Bạn có thể sử dụng python itertools.praduct để tạo kết quả tương tự.

from itertools import product

for _set in product(list('abc'), repeat=3):
    print(''.join(_set))

References:

  • https:
  • https://www.geeksforgeeks.org/print-all-permutations-with-repetition-of-characters/
  • https://www.geeksforgeeks.org/print-all-combinations-of-given-length/
  • https://www.geeksforgeeks.org/combinations-with-repetitions/
  • https://stackoverflow.com/questions/3099987/generating-permutations-with-repetitions-in-python

Cập nhật lần cuối vào ngày 19 tháng 8 năm 2022 21:50:47 (UTC/GMT +8 giờ)

Chuỗi Python: Tập thể dục-52 với giải pháp

Viết một chương trình Python để in tất cả các hoán vị với số lượng lặp lại số ký tự của một chuỗi nhất định.

Giải pháp mẫu:-:-

Mã Python:

from itertools import product
def all_repeat(str1, rno):
  chars = list(str1)
  results = []
  for c in product(chars, repeat = rno):
    results.append(c)
  return results
print(all_repeat('xyz', 3))
print(all_repeat('xyz', 2))
print(all_repeat('abcd', 4))

Đầu ra mẫu:

[('x', 'x', 'x'), ('x', 'x', 'y'), ('x', 'x', 'z'), ('x', 'y', 'x'), ('x', 'y', 'y'), ('x', 'y', 'z'), ('x', 'z', 'x'), ('x', 'z', 'y'), ('x', 'z', 'z'), ('y', 'x', 'x'), ('y', 'x', 'y'), ('y', 'x', 'z'), ('y', 'y', 'x'), ('y', 'y', 'y'), ('y', 'y', 'z'), ('y', 'z', 'x'), ('y', 'z', 'y'), ('y', 'z', 'z'), ('z', 'x', 'x'), ('z', 'x', 'y'), ('z', 'x', 'z'), ('z', 'y', 'x'), ('z', 'y', 'y'), ('z', 'y', 'z'), ('z', 'z', 'x'), ('z', 'z', 'y'), ('z', 'z', 'z')]
[('x', 'x'), ('x', 'y'), ('x', 'z'), ('y', 'x'), ('y', 'y'), ('y', 'z'), ('z', 'x'), ('z', 'y'), ('z', 'z')]
[('a', 'a', 'a', 'a'), ('a', 'a', 'a', 'b'), ('a', 'a', 'a', 'c'), ('a', 'a', 'a', 'd'), ('a', 'a', 'b', 'a'), ('a', 'a', 'b', 'b'), ('a', 'a', 'b', 'c'), ('a', 'a', 'b', 'd'), ('a', 'a', 'c', 'a'), ('a', 'a', 'c', 'b'), ('a', 'a', 'c', 'c'), ('a', 'a', 'c', 'd'), ('a', 'a', 'd', 'a'), ('a', 'a', 'd', 'b'), ('a', 'a', 'd', 'c'), ('a', 'a', 'd', 'd'), ('a', 'b', 'a', 'a'), ('a', 'b', 'a', 'b'), ('a', 'b', 'a', 'c'), ('a', 'b', 'a', 'd'), ('a', 'b', 'b', 'a'), ('a', 'b', 'b', 'b'), ('a', 'b', 'b', 'c'), ('a', 'b', 'b', 'd'), ('a', 'b', 'c', 'a'), ('a', 'b', 'c', 'b'), ('a', 'b', 'c', 'c'), ('a', 'b', 'c', 'd'), ('a', 'b', 'd', 'a'), ('a', 'b', 'd', 'b'), ('a', 'b', 'd', 'c'), ('a', 'b', 'd', 'd'), ('a', 'c', 'a', 'a'), ('a', 'c', 'a', 'b'), ('a', 'c', 'a', 'c'), ('a', 'c', 'a', 'd'), ('a', 'c', 'b', 'a'), ('a', 'c', 'b', 'b'), ('a', 'c', 'b', 'c'), ('a', 'c', 'b', 'd'), ('a', 'c', 'c', 'a'), ('a', 'c', 'c', 'b'), ('a', 'c', 'c', 'c'), ('a', 'c', 'c', 'd'), ('a', 'c', 'd', 'a'), ('a', 'c', 'd', 'b'), ('a', 'c', 'd', 'c'), ('a', 'c', 'd', 'd'), ('a', 'd', 'a', 'a'), ('a', 'd', 'a', 'b'), ('a', 'd', 'a', 'c'), ('a', 'd', 'a', 'd'), ('a', 'd', 'b', 'a'), ('a', 'd', 'b', 'b'), ('a', 'd', 'b', 'c'), ('a', 'd', 'b', 'd'), ('a', 'd', 'c', 'a'), ('a', 'd', 'c', 'b'), ('a', 'd', 'c', 'c'), ('a', 'd', 'c', 'd'), ('a', 'd', 'd', 'a'), ('a', 'd', 'd', 'b'), ('a', 'd', 'd', 'c'), ('a', 'd', 'd', 'd'), ('b', 'a', 'a', 'a'), ('b', 'a', 'a', 'b'), ('b', 'a', 'a', 'c'), ('b', 'a', 'a', 'd'), ('b', 'a', 'b', 'a'), ('b', 'a', 'b', 'b'), ('b', 'a', 'b', 'c'), ('b', 'a', 'b', 'd'), ('b', 'a', 'c', 'a'), ('b', 'a', 'c', 'b'), ('b', 'a', 'c', 'c'), ('b', 'a', 'c', 'd'), ('b', 'a', 'd', 'a'), ('b', 'a', 'd', 'b'), ('b', 'a', 'd', 'c'), ('b', 'a', 'd', 'd'), ('b', 'b', 'a', 'a'), ('b', 'b', 'a', 'b'), ('b', 'b', 'a', 'c'), ('b', 'b', 'a', 'd'), ('b', 'b', 'b', 'a'), ('b', 'b', 'b', 'b'), ('b', 'b', 'b', 'c'), ('b', 'b', 'b', 'd'), ('b', 'b', 'c', 'a'), ('b', 'b', 'c', 'b'), ('b', 'b', 'c', 'c'), ('b', 'b', 'c', 'd'), ('b', 'b', 'd', 'a'), ('b', 'b', 'd', 'b'), ('b', 'b', 'd', 'c'), ('b', 'b', 'd', 'd'), ('b', 'c', 'a', 'a'), ('b', 'c', 'a', 'b'), ('b', 'c', 'a', 'c'), ('b', 'c', 'a', 'd'), ('b', 'c', 'b', 'a'), ('b', 'c', 'b', 'b'), ('b', 'c', 'b', 'c'), ('b', 'c', 'b', 'd'), ('b', 'c', 'c', 'a'), ('b', 'c', 'c', 'b'), ('b', 'c', 'c', 'c'), ('b', 'c', 'c', 'd'), ('b', 'c', 'd', 'a'), ('b', 'c', 'd', 'b'), ('b', 'c', 'd', 'c'), ('b', 'c', 'd', 'd'), ('b', 'd', 'a', 'a'), ('b', 'd', 'a', 'b'), ('b', 'd', 'a', 'c'), ('b', 'd', 'a', 'd'), ('b', 'd', 'b', 'a'), ('b', 'd', 'b', 'b'), ('b', 'd', 'b', 'c'), ('b', 'd', 'b', 'd'), ('b', 'd', 'c', 'a'), ('b', 'd', 'c', 'b'), ('b', 'd', 'c', 'c'), ('b', 'd', 'c', 'd'), ('b', 'd', 'd', 'a'), ('b', 'd', 'd', 'b'), ('b', 'd', 'd', 'c'), ('b', 'd', 'd', 'd'), ('c', 'a', 'a', 'a'), ('c', 'a', 'a', 'b'), ('c', 'a', 'a', 'c'), ('c', 'a', 'a', 'd'), ('c', 'a', 'b', 'a'), ('c', 'a', 'b', 'b'), ('c', 'a', 'b', 'c'), ('c', 'a', 'b', 'd'), ('c', 'a', 'c', 'a'), ('c', 'a', 'c', 'b'), ('c', 'a', 'c', 'c'), ('c', 'a', 'c', 'd'), ('c', 'a', 'd', 'a'), ('c', 'a', 'd', 'b'), ('c', 'a', 'd', 'c'), ('c', 'a', 'd', 'd'), ('c', 'b', 'a', 'a'), ('c', 'b', 'a', 'b'), ('c', 'b', 'a', 'c'), ('c', 'b', 'a', 'd'), ('c', 'b', 'b', 'a'), ('c', 'b', 'b', 'b'), ('c', 'b', 'b', 'c'), ('c', 'b', 'b', 'd'), ('c', 'b', 'c', 'a'), ('c', 'b', 'c', 'b'), ('c', 'b', 'c', 'c'), ('c', 'b', 'c', 'd'), ('c', 'b', 'd', 'a'), ('c', 'b', 'd', 'b'), ('c', 'b', 'd', 'c'), ('c', 'b', 'd', 'd'), ('c', 'c', 'a', 'a'), ('c', 'c', 'a', 'b'), ('c', 'c', 'a', 'c'), ('c', 'c', 'a', 'd'), ('c', 'c', 'b', 'a'), ('c', 'c', 'b', 'b'), ('c', 'c', 'b', 'c'), ('c', 'c', 'b', 'd'), ('c', 'c', 'c', 'a'), ('c', 'c', 'c', 'b'), ('c', 'c', 'c', 'c'), ('c', 'c', 'c', 'd'), ('c', 'c', 'd', 'a'), ('c', 'c', 'd', 'b'), ('c', 'c', 'd', 'c'), ('c', 'c', 'd', 'd'), ('c', 'd', 'a', 'a'), ('c', 'd', 'a', 'b'), ('c', 'd', 'a', 'c'), ('c', 'd', 'a', 'd'), ('c', 'd', 'b', 'a'), ('c', 'd', 'b', 'b'), ('c', 'd', 'b', 'c'), ('c', 'd', 'b', 'd'), ('c', 'd', 'c', 'a'), ('c', 'd', 'c', 'b'), ('c', 'd', 'c', 'c'), ('c', 'd', 'c', 'd'), ('c', 'd', 'd', 'a'), ('c', 'd', 'd', 'b'), ('c', 'd', 'd', 'c'), ('c', 'd', 'd', 'd'), ('d', 'a', 'a', 'a'), ('d', 'a', 'a', 'b'), ('d', 'a', 'a', 'c'), ('d', 'a', 'a', 'd'), ('d', 'a', 'b', 'a'), ('d', 'a', 'b', 'b'), ('d', 'a', 'b', 'c'), ('d', 'a', 'b', 'd'), ('d', 'a', 'c', 'a'), ('d', 'a', 'c', 'b'), ('d', 'a', 'c', 'c'), ('d', 'a', 'c', 'd'), ('d', 'a', 'd', 'a'), ('d', 'a', 'd', 'b'), ('d', 'a', 'd', 'c'), ('d', 'a', 'd', 'd'), ('d', 'b', 'a', 'a'), ('d', 'b', 'a', 'b'), ('d', 'b', 'a', 'c'), ('d', 'b', 'a', 'd'), ('d', 'b', 'b', 'a'), ('d', 'b', 'b', 'b'), ('d', 'b', 'b', 'c'), ('d', 'b', 'b', 'd'), ('d', 'b', 'c', 'a'), ('d', 'b', 'c', 'b'), ('d', 'b', 'c', 'c'), ('d', 'b', 'c', 'd'), ('d', 'b', 'd', 'a'), ('d', 'b', 'd', 'b'), ('d', 'b', 'd', 'c'), ('d', 'b', 'd', 'd'), ('d', 'c', 'a', 'a'), ('d', 'c', 'a', 'b'), ('d', 'c', 'a', 'c'), ('d', 'c', 'a', 'd'), ('d', 'c', 'b', 'a'), ('d', 'c', 'b', 'b'), ('d', 'c', 'b', 'c'), ('d', 'c', 'b', 'd'), ('d', 'c', 'c', 'a'), ('d', 'c', 'c', 'b'), ('d', 'c', 'c', 'c'), ('d', 'c', 'c', 'd'), ('d', 'c', 'd', 'a'), ('d', 'c', 'd', 'b'), ('d', 'c', 'd', 'c'), ('d', 'c', 'd', 'd'), ('d', 'd', 'a', 'a'), ('d', 'd', 'a', 'b'), ('d', 'd', 'a', 'c'), ('d', 'd', 'a', 'd'), ('d', 'd', 'b', 'a'), ('d', 'd', 'b', 'b'), ('d', 'd', 'b', 'c'), ('d', 'd', 'b', 'd'), ('d', 'd', 'c', 'a'), ('d', 'd', 'c', 'b'), ('d', 'd', 'c', 'c'), ('d', 'd', 'c', 'd'), ('d', 'd', 'd', 'a'), ('d', 'd', 'd', 'b'), ('d', 'd', 'd', 'c'), ('d', 'd', 'd', 'd')]          

Trình bày bằng hình ảnh:

Flowchart:

Hướng dẫn permutation with repeated elements python - hoán vị với các phần tử lặp lại python

Trực quan hóa thực thi mã Python:

Công cụ sau đây trực quan hóa những gì máy tính đang làm từng bước khi nó thực hiện chương trình đã nói:

Trình chỉnh sửa mã Python:

Có một cách khác để giải quyết giải pháp này?Đóng góp mã của bạn (và nhận xét) thông qua Disqus.

Trước đây: Viết chương trình Python để tìm ký tự không lặp lại đầu tiên trong chuỗi đã cho.next: viết một chương trình Python để tìm ký tự lặp lại đầu tiên trong một chuỗi nhất định. Write a Python program to find the first non-repeating character in given string.
Next:Write a Python program to find the first repeated character in a given string.