반복으로 순열 생성

반복으로 순열 생성

---

itertools에 대해 알고 있지만 반복없이 순열 만 생성 할 수있는 것 같습니다.

예를 들어, 2 개의 주사위에 대해 가능한 모든 주사위 굴림을 생성하고 싶습니다. 따라서 반복을 포함하여 [1, 2, 3, 4, 5, 6] 크기 2의 모든 순열이 필요합니다 : (1, 1), (1, 2), (2, 1) ... 등

가능하다면 처음부터 구현하고 싶지 않습니다.

---

Cartesian Product를 찾고 있습니다.

수학에서 데카르트 곱 (또는 제품 세트)은 두 세트의 직접 곱입니다.

귀하의 경우 이것은 {1, 2, 3, 4, 5, 6}x {1, 2, 3, 4, 5, 6}입니다. itertools거기에서 당신을 도울 수 있습니다 :

import itertools
x = [1, 2, 3, 4, 5, 6]
[p for p in itertools.product(x, repeat=2)]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), 
 (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), 
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), 
 (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

무작위 주사위 굴림을 얻으려면 ( 완전히 비효율적 인 방식으로 ) :

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)

---

순열을 찾는 것이 아니라 Cartesian Product 를 원합니다 . itertools 의이 사용 제품 :

from itertools import product
for roll in product([1, 2, 3, 4, 5, 6], repeat = 2):
    print(roll)

---

파이썬 2.7과 3.1에는 itertools.combinations_with_replacement함수가 있습니다 :

>>> list(itertools.combinations_with_replacement([1, 2, 3, 4, 5, 6], 2))
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4), 
 (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6),
 (5, 5), (5, 6), (6, 6)]

---

이 경우 목록 이해력은 특별히 필요하지 않습니다.

주어진

import itertools as it


iter_ = range(1, 7)
r = 2

암호

list(it.product(iter_, repeat=r))

---

세부

당연히 데카르트 곱은 순열의 하위 집합을 생성 할 수 있습니다. 그러나 다음과 같습니다.

• 대체로 : 하나는 다음을 통해 모든 순열을 생성 할 수 있습니다. product
• 교체없이 : 후자에서 필터링 할 수 있습니다.

대체가있는 순열, n ** r

[x for x in it.product(iter_, repeat=r)]

대체없는 순열, n!

[x for x in it.product(iter_, repeat=r) if len(set(x)) == r]

# Equivalent
list(it.permutations(iter_, r))  

---

먼저 itertools.permutations (list)에서 반환 한 생성기를 목록으로 먼저 전환해야합니다. 그런 다음 두 번째로 set ()를 사용하여 중복을 제거 할 수 있습니다.

def permutate(a_list):
    import itertools
    return set(list(itertools.permutations(a_list)))

---

다음은 참조 용으로 C # 버전입니다 (python을 요청했지만 알고리즘은 동일해야 함).

아래 방법은 기본적으로 없습니다. 다양한 순열에 도달하기 위해 주사위를 던질 수 있습니다. 위 질문의 경우 크기는 '2'여야합니다.

private void GetAllPermutationsOfDice_Recursive(int size, string currentValue, 
            List<string> values)
        {
            if(currentValue.Length == size)
            {
                values.Add(currentValue);
                return;
            }
            for(int i = 1; i<=6;i++)
            {
                this.GetAllPermutationsOfDice_Recursive(size, currentValue + i, values);   
            }
        }

주사위를 두 번 던지기 위해 위의 메서드를 다음과 같이 호출 할 수 있습니다.

public string[] GetAllPermutationsOfDiceOfSize_2()
        {
            List<string> values = new List<string>();
            this.GetAllPermutationsOfDice_Recursive(2, "", values);
            return values.ToArray();
        }

다음은 해당 단위 테스트입니다.

[TestMethod]
        public void Dice_PermutationsTests()
        {
            var v = this.GetAllPermutationsOfDiceOfSize_2();
            Assert.AreEqual(36, v.Length);
            int l = 6;
            List<string> values = new List<string>();
            for(int i = 1; i<=4; i++)
            {
                values.Clear();
                this.GetAllPermutationsOfDice_Recursive(i, "", values);
                Assert.AreEqual(l, values.Count);
                l *= 6;
            }
        }

참고 URL : https://stackoverflow.com/questions/3099987/generating-permutations-with-repetitions