주어진 길이의 k의 순열을 찾는 방법은 무엇입니까?

Question

주어진 길이에서 k의 순열을 어떻게 찾을 수 있습니까? 예를 들어

:

단어 cat 3 편지를 가지고 : 나는 단어 cat 2의 모든 순열을 찾을 수있는 방법. 결과는 다음과 같아야합니다 ac, at, ca, ac, 등등 ...

---

이 숙제 문제가되지 않습니다. 모든 언어를 사용할 수 있지만 C/C++ 또는 C#이 더 바람직합니다. 길이가 LENGTH 인 재귀를 만드는 방법을 알고 있지만 사용자 정의 크기를 만드는 방법은 알지 못합니다.

Answer 1

반복 문자로도 작동합니다 C#의 하나입니다. 길이 2의 순열을위한 "바나나"에 대한 예를 들어 그것을 제공 : AB의 AA 억

바에게주의를 노나 윈

기본적인 아이디어는 다음, 첫 번째 문자를 고정 길이의 모든 순열을 형성하는

k-1, 그 k-1 길이 순열에 문자를 앞에 붙이십시오. 중복 된 문자를 처리하기 위해 왼쪽에있는 개수 (즉, 하위 순열에 사용할 수있는 개수)를 추적합니다.

예제 코드는 아니지만 아이디어를 제공해야합니다. 버그를 발견하면 알려주고 편집 할 수 있습니다.

static List<string> Permutations(Dictionary<char, int> input, int length) { 
    List<string> permutations = new List<string>(); 

    List<char> chars = new List<char>(input.Keys); 

    // Base case. 
    if (length == 0) { 
     permutations.Add(string.Empty); 
     return permutations; 
    } 

    foreach (char c in chars) { 

     // There are instances of this character left to use. 
     if (input[c] > 0) { 

      // Use one instance up. 
      input[c]--; 

      // Find sub-permutations of length length -1. 
      List<string> subpermutations = Permutations(input, length - 1); 

      // Give back the instance. 
      input[c]++; 

      foreach (string s in subpermutations) { 

       // Prepend the character to be the first character. 
       permutations.Add(s.Insert(0,new string(c,1))); 

      } 
     } 
    } 

    return permutations; 
} 

그리고 여기가 내가 가지고있는 전체 프로그램입니다, 그것을 사용하는 : 내가 잘못 본게 아니라면

using System; 
using System.Collections.Generic; 

namespace StackOverflow { 

    class Program { 
     static void Main(string[] args) { 
      List<string> p = Permutations("abracadabra", 3); 
      foreach (string s in p) { 
       Console.WriteLine(s); 
      } 
     } 

     static List<string> Permutations(string s, int length) { 
      Dictionary<char, int> input = new Dictionary<char, int>(); 
      foreach (char c in s) { 
       if (input.ContainsKey(c)) { 
        input[c]++; 
       } else { 
        input[c] = 1; 
       } 
      } 
      return Permutations(input, length); 
     } 

     static List<string> Permutations(Dictionary<char, int> input, 
                  int length) { 
      List<string> permutations = new List<string>(); 

      List<char> chars = new List<char>(input.Keys); 
      if (length == 0) { 
       permutations.Add(string.Empty); 
       return permutations; 
      } 

      foreach (char c in chars) { 
       if (input[c] > 0) { 
        input[c]--; 
        List<string> subpermutations = Permutations(input, 
                   length - 1); 
        input[c]++; 

        foreach (string s in subpermutations) { 
         permutations.Add(s.Insert(0,new string(c,1))); 
        } 
       } 
      } 

      return permutations; 
     } 
    } 
} 

Answer 2

재귀 적 솔루션에 문제가있어서 여분의 매개 변수 (깊이)를 전달하므로 재귀 함수가 깊이> n 인 경우 즉시 반환됩니다.

Answer 3

가장 효율적인 아니,하지만 작동 :

여기

public class permutation 
{ 
    public static List<string> getPermutations(int n, string word) 
    { 
     List<string> tmpPermutation = new List<string>(); 
     if (string.IsNullOrEmpty(word) || n <= 0) 
     { 
      tmpPermutation.Add(""); 
     } 
     else 
     { 
      for (int i = 0; i < word.Length; i++) 
      { 
       string tmpWord = word.Remove(i, 1); 
       foreach (var item in getPermutations(n - 1, tmpWord)) 
       { 
        tmpPermutation.Add(word[i] + item); 
       } 
      } 
     } 
     return tmpPermutation; 
    } 
} 

Answer 4

,이 문제는 http://en.wikipedia.org/wiki/Combinadic/에로, 너무 combinadics에 의해 해결 될 수있다, 참조있다 거기도 구현합니다.

일련의 숫자에서 가능한 모든 트리플을 생성하기 위해 Java 솔루션 (http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/)을 직접 사용했습니다. 이는 다를 수 없습니다.

내가 배후에 수학을 설명하는 데 부족함이 있지만 이것이 이해할 수있는 한, 컬렉션 내에서 가능한 모든 nCr (예 : 고양이의 경우 3C2) 선택을 반복하는 가장 복잡한 방법입니다.

Answer 5

먼저 배열의 가능한 하위 집합을 찾습니다. 당신은 두 번째로 내가 그것을 구현하지 않은하지만 난 그것을 작동합니다 생각 STL-알고리즘 next_permutation

으로 모든 부분 집합의 순열을 계산 Iterating over subsets of any size

에 에서 논의 된 재귀 방식으로이 작업을 수행 할 수 있습니다.

Answer 6

void Prem (char *str, int k, int length) { 
    if (k == length-1){ 
     printf("%s\n",str); 
     return; 
    } else { 
     for (int i = k ; i < length; ++i) { 
      char t = str[k]; 
      str[k] = str[i]; 
      str[i] = t; 
      Prem(str,k+1,length); 
      t = str[k]; 
      str[k] = str[i]; 
      str[i] = t; 
     } 
    } 
}