문자열의 가능한 모든 순열 목록 생성

Question

가변 문자 목록을 포함하여 길이가 x와 y 문자 사이에 있는 문자열의 가능한 모든 순열 목록을 생성하려면 어떻게 해야 합니까?

모든 언어가 작동하지만 이식성이 있어야 합니다.

Answer 1

이를 수행하는 방법에는 여러 가지가 있습니다.일반적인 방법은 재귀, 메모 또는 동적 프로그래밍을 사용합니다.기본 아이디어는 길이가 1인 모든 문자열의 목록을 생성한 다음 각 반복에서 마지막 반복에서 생성된 모든 문자열에 대해 문자열의 각 문자와 연결된 해당 문자열을 개별적으로 추가하는 것입니다.(아래 코드의 변수 인덱스는 마지막 반복의 시작과 다음 반복을 추적합니다)

일부 의사코드:

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

그런 다음 길이가 x보다 작은 모든 문자열을 제거해야 하며 목록의 첫 번째 (x-1) * len(originalString) 항목이 됩니다.

Answer 2

역추적을 사용하는 것이 더 좋습니다.

#include <stdio.h>
#include <string.h>

void swap(char *a, char *b) {
    char temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void print(char *a, int i, int n) {
    int j;
    if(i == n) {
        printf("%s\n", a);
    } else {
        for(j = i; j <= n; j++) {
            swap(a + i, a + j);
            print(a, i + 1, n);
            swap(a + i, a + j);
        }
    }
}

int main(void) {
    char a[100];
    gets(a);
    print(a, 0, strlen(a) - 1);
    return 0;
}

Answer 3

당신은 많은 문자열을 얻게 될 것입니다. 그것은 확실합니다 ...

\sum_{i=x}^y{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D
여기서 x와 y는 정의하는 방법이고 r은 우리가 선택하는 문자의 수입니다. 제가 올바르게 이해하고 있는 경우입니다.필요에 따라 이를 생성해야 하며 엉성하게 파워셋을 생성한 다음 문자열 길이를 필터링해서는 안 됩니다.

다음은 이를 생성하는 가장 좋은 방법은 아니지만 그럼에도 불구하고 흥미로운 점입니다.

Knuth(4권, Fasicle 2, 7.2.1.3)는 (s,t)-조합이 s+1개의 항목을 반복하여 한 번에 취하는 것과 동일하다고 말합니다. (s,t)-조합은 다음에 사용되는 표기법입니다. Knuth는 다음과 같습니다. {t \선택 {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.먼저 각 (s,t) 조합을 이진 형식(즉 길이가 (s+t))으로 생성하고 각 1 왼쪽에 있는 0의 수를 세어 이를 알아낼 수 있습니다.

10001000011101 --> 순열이 됩니다.{0, 3, 4, 4, 4, 1}

Answer 4

Knuth, Python 예제에 따른 비재귀 솔루션:

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]<perm[i+1]:
            k0=i
    if k0 == None:
        return None

    l0 = k0+1
    for i in range(k0+1, len(perm)):
        if perm[k0] < perm[i]:
            l0 = i

    perm[k0], perm[l0] = perm[l0], perm[k0]
    perm[k0+1:] = reversed(perm[k0+1:])
    return perm

perm=list("12345")
while perm:
    print perm
    perm = nextPermutation(perm)

Answer 5

"라고 보시면 될 것 같습니다.집합의 하위 집합을 효율적으로 열거하기"는 원하는 작업의 일부를 수행하는 알고리즘을 설명합니다. 길이 x에서 y까지 N 문자의 모든 하위 집합을 빠르게 생성합니다.여기에는 C로 구현된 내용이 포함되어 있습니다.

각 하위 집합에 대해 여전히 모든 순열을 생성해야 합니다.예를 들어 "abcde"에서 3개의 문자를 원하는 경우 이 알고리즘은 "abc","abd", "abe"...를 제공합니다.하지만 "acb", "bac", "bca" 등을 얻으려면 각각을 순열해야 합니다.

Answer 6

다음을 기반으로 작동하는 일부 Java 코드 사프의 대답:

public class permute {

    static void permute(int level, String permuted,
                    boolean used[], String original) {
        int length = original.length();
        if (level == length) {
            System.out.println(permuted);
        } else {
            for (int i = 0; i < length; i++) {
                if (!used[i]) {
                    used[i] = true;
                    permute(level + 1, permuted + original.charAt(i),
                       used, original);
                    used[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = "hello";
        boolean used[] = {false, false, false, false, false};
        permute(0, "", used, s);
    }
}

Answer 7

다음은 C#의 간단한 솔루션입니다.

주어진 문자열의 고유한 순열만 생성합니다.

    static public IEnumerable<string> permute(string word)
    {
        if (word.Length > 1)
        {

            char character = word[0];
            foreach (string subPermute in permute(word.Substring(1)))
            {

                for (int index = 0; index <= subPermute.Length; index++)
                {
                    string pre = subPermute.Substring(0, index);
                    string post = subPermute.Substring(index);

                    if (post.Contains(character))
                            continue;                       

                    yield return pre + character + post;
                }

            }
        }
        else
        {
            yield return word;
        }
    }

Answer 8

여기에는 좋은 답변이 많이 있습니다.또한 C++에서 매우 간단한 재귀 솔루션을 제안합니다.

#include <string>
#include <iostream>

template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
    if (start == s.length()) consume(s);
    for (std::size_t i = start; i < s.length(); i++) {
        std::swap(s[start], s[i]);
        permutations(s, consume, start + 1);
    }
}

int main(void) {
    std::string s = "abcd";
    permutations(s, [](std::string s) {
        std::cout << s << std::endl;
    });
}

메모:반복되는 문자가 포함된 문자열은 고유한 순열을 생성하지 않습니다.

Answer 9

방금 Ruby에서 이것을 빠르게 작성했습니다.

def perms(x, y, possible_characters)
  all = [""]
  current_array = all.clone
  1.upto(y) { |iteration|
    next_array = []
    current_array.each { |string|
      possible_characters.each { |c|
        value = string + c
        next_array.insert next_array.length, value
        all.insert all.length, value
      }
    }
    current_array = next_array
  }
  all.delete_if { |string| string.length < x }
end

내장된 순열 유형 함수에 대한 언어 API를 살펴볼 수도 있고 더 최적화된 코드를 작성할 수도 있지만 숫자가 너무 높으면 많은 결과를 얻을 수 있는 방법이 많지 않을 것입니다. .

어쨌든 코드의 기본 아이디어는 길이가 0인 문자열로 시작한 다음 길이가 Z인 모든 문자열을 추적하는 것입니다. 여기서 Z는 반복의 현재 크기입니다.그런 다음 각 문자열을 살펴보고 각 문자열에 각 문자를 추가합니다.마지막으로 x 임계값 아래에 있는 항목을 모두 제거하고 결과를 반환합니다.

잠재적으로 의미가 없는 입력(널 문자 목록, 이상한 x 및 y 값 등)으로 테스트하지 않았습니다.

Answer 10

이것은 Mike의 Ruby 버전을 Common Lisp로 번역한 것입니다:

(defun perms (x y original-string)
  (loop with all = (list "")
        with current-array = (list "")
        for iteration from 1 to y
        do (loop with next-array = nil
                 for string in current-array
                 do (loop for c across original-string
                          for value = (concatenate 'string string (string c))
                          do (push value next-array)
                             (push value all))
                    (setf current-array (reverse next-array)))
        finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))

약간 더 짧고 더 많은 루프 기능을 사용하는 또 다른 버전은 다음과 같습니다.

(defun perms (x y original-string)
  (loop repeat y
        collect (loop for string in (or (car (last sets)) (list ""))
                      append (loop for c across original-string
                                   collect (concatenate 'string string (string c)))) into sets
        finally (return (loop for set in sets
                              append (loop for el in set when (>= (length el) x) collect el)))))

Answer 11

다음은 간단한 단어 C# 재귀 솔루션입니다.

방법:

public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
        {
            bool finished = true;
            ArrayList newWords = new ArrayList();
            if (words.Count == 0)
            {
                foreach (string letter in letters)
                {
                    words.Add(letter);
                }
            }

            for(int j=index; j<words.Count; j++)
            {
                string word = (string)words[j];
                for(int i =0; i<letters.Length; i++)
                {
                    if(!word.Contains(letters[i]))
                    {
                        finished = false;
                        string newWord = (string)word.Clone();
                        newWord += letters[i];
                        newWords.Add(newWord);
                    }
                }
            }

            foreach (string newWord in newWords)
            {   
                words.Add(newWord);
            }

            if(finished  == false)
            {
                CalculateWordPermutations(letters, words, words.Count - newWords.Count);
            }
            return words;
        }

부름:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);

Answer 12

Perl에서는 소문자 알파벳만 사용하고 싶다면 다음과 같이 하면 됩니다:

my @result = ("a" .. "zzzz");

이는 소문자를 사용하여 1~4자 사이의 가능한 모든 문자열을 제공합니다.대문자의 경우 변경 "a" 에게 "A" 그리고 "zzzz" 에게 "ZZZZ".

대소문자가 혼합된 경우 훨씬 더 어려워지고 Perl의 내장 연산자 중 하나를 사용하면 아마도 불가능할 것입니다.

Answer 13

...C 버전은 다음과 같습니다.

void permute(const char *s, char *out, int *used, int len, int lev)
{
    if (len == lev) {
        out[lev] = '\0';
        puts(out);
        return;
    }

    int i;
    for (i = 0; i < len; ++i) {
        if (! used[i])
            continue;

        used[i] = 1;
        out[lev] = s[i];
        permute(s, out, used, len, lev + 1);
        used[i] = 0;
    }
    return;
}

Answer 14

순열(ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*비기), (기비*)] -> [(*ㅏ기원전), (비ㅏ다), (기원전ㅏ*), (*ㅏCB), (Cㅏ나), (CBㅏ*)]] 각 알파벳 점검을 삽입 할 때 중복을 제거하려면 이전 문자열이 동일한 알파벳으로 끝나는 지 확인하십시오 (왜?-운동)

public static void main(String[] args) {

    for (String str : permStr("ABBB")){
        System.out.println(str);
    }
}

static Vector<String> permStr(String str){

    if (str.length() == 1){
        Vector<String> ret = new Vector<String>();
        ret.add(str);
        return ret;
    }

    char start = str.charAt(0);
    Vector<String> endStrs = permStr(str.substring(1));
    Vector<String> newEndStrs = new Vector<String>();
    for (String endStr : endStrs){
        for (int j = 0; j <= endStr.length(); j++){
            if (endStr.substring(0, j).endsWith(String.valueOf(start)))
                break;
            newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
        }
    }
    return newEndStrs;
}

중복이 없는 모든 순열을 인쇄합니다.

Answer 15

작동하는 Ruby 답변 :

class String
  def each_char_with_index
    0.upto(size - 1) do |index|
      yield(self[index..index], index)
    end
  end
  def remove_char_at(index)
    return self[1..-1] if index == 0
    self[0..(index-1)] + self[(index+1)..-1]
  end
end

def permute(str, prefix = '')
  if str.size == 0
    puts prefix
    return
  end
  str.each_char_with_index do |char, index|
    permute(str.remove_char_at(index), prefix + char)
  end
end

# example
# permute("abc")

Answer 16

C++의 재귀 솔루션

int main (int argc, char * const argv[]) {
        string s = "sarp";
        bool used [4];
        permute(0, "", used, s);
}

void permute(int level, string permuted, bool used [], string &original) {
    int length = original.length();

    if(level == length) { // permutation complete, display
        cout << permuted << endl;
    } else {
        for(int i=0; i<length; i++) { // try to add an unused character
            if(!used[i]) {
                used[i] = true;
                permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
                used[i] = false;
            }
        }
}

Answer 17

다음 Java 재귀는 주어진 문자열의 모든 순열을 인쇄합니다.

//call it as permut("",str);

public void permut(String str1,String str2){
    if(str2.length() != 0){
        char ch = str2.charAt(0);
        for(int i = 0; i <= str1.length();i++)
            permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                     str2.substring(1,str2.length()));
    }else{
    System.out.println(str1);
    }
}

다음은 n!을 만드는 위의 "permut" 메서드의 업데이트된 버전입니다.(n 계승) 위의 방법에 비해 덜 재귀적인 호출

//call it as permut("",str);

public void permut(String str1,String str2){
   if(str2.length() > 1){
       char ch = str2.charAt(0);
       for(int i = 0; i <= str1.length();i++)
          permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }else{
    char ch = str2.charAt(0);
    for(int i = 0; i <= str1.length();i++)
        System.out.println(str1.substring(0,i) + ch +    str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }
}

Answer 18

import java.util.*;

public class all_subsets {
    public static void main(String[] args) {
        String a = "abcd";
        for(String s: all_perm(a)) {
            System.out.println(s);
        }
    }

    public static Set<String> concat(String c, Set<String> lst) {
        HashSet<String> ret_set = new HashSet<String>();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet<String> all_perm(String a) {
        HashSet<String> set = new HashSet<String>();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i<a.length(); i++) {
                set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
            }
        }
        return set;
    }
}

Answer 19

다음은 제가 생각해낸 비재귀 버전입니다. 자바스크립트로 말이죠.위의 Knuth의 비재귀적 방법을 기반으로 한 것은 아니지만 요소 교환에 일부 유사점이 있습니다.최대 8개 요소의 입력 배열에 대한 정확성을 확인했습니다.

빠른 최적화는 사전 비행입니다. out 배열 및 회피 push().

기본 아이디어는 다음과 같습니다.

1. 단일 소스 배열이 주어지면 첫 번째 요소를 각 후속 요소와 차례로 교체하는 첫 번째 새 배열 세트를 생성하고 매번 다른 요소는 교란되지 않은 상태로 둡니다.예:1234가 주어지면 1234, 2134, 3214, 4231이 생성됩니다.

2. 이전 패스의 각 배열을 새 패스의 시드로 사용하지만 첫 번째 요소를 바꾸는 대신 두 번째 요소를 각 후속 요소로 바꿉니다.또한 이번에는 출력에 원래 배열을 포함하지 마세요.

3. 완료될 때까지 2단계를 반복합니다.

코드 샘플은 다음과 같습니다.

function oxe_perm(src, depth, index)
{
    var perm = src.slice();     // duplicates src.
    perm = perm.split("");
    perm[depth] = src[index];
    perm[index] = src[depth];
    perm = perm.join("");
    return perm;
}

function oxe_permutations(src)
{
    out = new Array();

    out.push(src);

    for (depth = 0; depth < src.length; depth++) {
        var numInPreviousPass = out.length;
        for (var m = 0; m < numInPreviousPass; ++m) {
            for (var n = depth + 1; n < src.length; ++n) {
                out.push(oxe_perm(out[m], depth, n));
            }
        }
    }

    return out;
}

Answer 20

애초에 왜 이 작업을 하려는지 잘 모르겠습니다.적당히 큰 x 및 y 값에 대한 결과 집합은 거대하며 x 및/또는 y가 커질수록 기하급수적으로 증가합니다.

가능한 문자 세트가 알파벳의 26개 소문자이고 길이가 5인 모든 순열을 생성하도록 애플리케이션에 요청한다고 가정해 보겠습니다.메모리가 부족하지 않다고 가정하면 11,881,376(예:26의 5승 거듭제곱입니다.해당 길이를 6으로 늘리면 308,915,776개의 문자열을 다시 얻게 됩니다.이 숫자는 매우 빠르게 고통스러울 정도로 커집니다.

다음은 Java로 구성한 솔루션입니다.두 개의 런타임 인수(x 및 y에 해당)를 제공해야 합니다.재미있게 보내세요.

public class GeneratePermutations {
    public static void main(String[] args) {
        int lower = Integer.parseInt(args[0]);
        int upper = Integer.parseInt(args[1]);

        if (upper < lower || upper == 0 || lower == 0) {
            System.exit(0);
        }

        for (int length = lower; length <= upper; length++) {
            generate(length, "");
        }
    }

    private static void generate(int length, String partial) {
        if (length <= 0) {
            System.out.println(partial);
        } else {
            for (char c = 'a'; c <= 'z'; c++) {
                generate(length - 1, partial + c);
            }
        }
    }
}

Answer 21

나는 오늘 이것이 필요했고 이미 주어진 답변이 나에게 올바른 방향을 제시했지만 그것은 내가 원하는 것과는 달랐습니다.

다음은 Heap의 메소드를 사용한 구현입니다.배열의 길이는 3 이상이어야 하며, 수행하려는 작업, 인내심 및 클럭 속도에 따라 실제 고려 사항으로 10보다 크지 않아야 합니다.

루프에 들어가기 전에 초기화하십시오. Perm(1 To N) 첫 번째 순열로, Stack(3 To N) 0*을 사용하고, Level ~와 함께 2**.루프 호출이 끝나면 NextPerm, 완료되면 false를 반환합니다.

* VB가 대신해 드립니다.

** NextPerm을 약간 변경하여 이를 불필요하게 만들 수 있지만 이렇게 하면 더 명확해집니다.

Option Explicit

Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
    Swap Perm(1), Perm(2)
    Level = 3
Else
    While Stack(Level) = Level - 1
        Stack(Level) = 0
        If Level = UBound(Stack) Then Exit Function
        Level = Level + 1
    Wend
    Stack(Level) = Stack(Level) + 1
    If Level And 1 Then N = 1 Else N = Stack(Level)
    Swap Perm(N), Perm(Level)
    Level = 2
End If
NextPerm = True
End Function

Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub

'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
    A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
    If CurrentY + TextHeight("0") > ScaleHeight Then
        ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
        CurrentY = 0
        CurrentX = 0
    End If
    T = vbNullString
    For I = 1 To UBound(A)
        Print A(I);
        T = T & Hex(A(I))
    Next
    Print
    Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
    J = J * I
Next
If J <> Test.Count Then Stop
End Sub

다른 방법은 다양한 저자에 의해 설명됩니다.Knuth는 두 가지를 설명하는데, 하나는 어휘 순서를 제공하지만 복잡하고 느리고, 다른 하나는 일반 변경 방법으로 알려져 있습니다.Jie Gao와 Dianjun Wang도 흥미로운 논문을 썼습니다.

Answer 22

루비에서:

str = "a"
100_000_000.times {puts str.next!}

꽤 빠르지만 시간이 좀 걸릴 것 같습니다 =).물론 짧은 문자열이 마음에 들지 않으면 "aaaaaaaa"부터 시작할 수도 있습니다.

실제 질문을 잘못 해석했을 수도 있습니다. 게시물 중 하나에서는 무차별 문자열 라이브러리가 필요한 것처럼 들렸지만 주요 질문에서는 특정 문자열을 순열해야 하는 것처럼 들립니다.

귀하의 문제는 다음과 다소 유사합니다. http://beust.com/weblog/archives/000491.html (숫자가 반복되지 않는 모든 정수를 나열하면 순열을 사용하는 ocaml 녀석과 또 다른 솔루션을 사용하는 일부 java 녀석과 함께 많은 언어가 문제를 해결하게 됩니다.)

Answer 23

다음 코드는 Python으로 호출할 때 allowed_characters 로 설정 [0,1] 최대 4자이면 2^4개의 결과가 생성됩니다.

['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

def generate_permutations(chars = 4) :

#modify if in need!
    allowed_chars = [
        '0',
        '1',
    ]

    status = []
    for tmp in range(chars) :
        status.append(0)

    last_char = len(allowed_chars)

    rows = []
    for x in xrange(last_char ** chars) :
        rows.append("")
        for y in range(chars - 1 , -1, -1) :
            key = status[y]
            rows[x] = allowed_chars[key] + rows[x]

        for pos in range(chars - 1, -1, -1) :
            if(status[pos] == last_char - 1) :
                status[pos] = 0
            else :
                status[pos] += 1
                break;

    return rows

import sys


print generate_permutations()

이것이 당신에게 도움이 되기를 바랍니다.숫자뿐만 아니라 모든 문자와 함께 작동합니다.

Answer 24

다음은 문자열의 순열을 인쇄하는 방법을 설명하는 링크입니다.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Answer 25

이것이 귀하의 질문에 정확하게 대답하지는 않지만 동일한 길이의 여러 문자열에서 문자의 모든 순열을 생성하는 한 가지 방법은 다음과 같습니다.예를 들어, 단어가 "coffee", "joomla" 및 "moodle"인 경우 "coodle", "joodee", "joffle" 등과 같은 결과가 나올 것으로 예상할 수 있습니다.

기본적으로 조합 수는 (단어 수)의 (단어당 문자 수)의 제곱입니다.따라서 0과 조합 수 - 1 사이에서 임의의 숫자를 선택하고 해당 숫자를 기본(단어 수)으로 변환한 다음 해당 숫자의 각 숫자를 다음 문자를 가져올 단어에 대한 표시기로 사용하십시오.

예:위의 예에서.단어 3개, 글자 6개 = 729개의 조합.임의의 숫자를 선택하세요:465.기본 3으로 변환:122020.단어 1의 첫 번째 문자, 단어 2의 두 번째 문자, 단어 2의 세 번째 문자, 단어 0의 네 번째 문자를 가져옵니다.그리고 당신은 ..."주플".

모든 순열을 원하면 0에서 728까지 반복하면 됩니다.물론, 무작위로 하나의 값을 선택하는 경우에는 더 간단하다 덜 혼란스러운 방법은 글자를 반복하는 것입니다.이 방법을 사용하면 모든 순열을 원할 경우 재귀를 피할 수 있으며 수학을 아는 것처럼 보이게 할 수 있습니다.^(tm)!

조합 수가 너무 많으면 일련의 작은 단어로 나누고 끝에 연결할 수 있습니다.

Answer 26

C# 반복:

public List<string> Permutations(char[] chars)
    {
        List<string> words = new List<string>();
        words.Add(chars[0].ToString());
        for (int i = 1; i < chars.Length; ++i)
        {
            int currLen = words.Count;
            for (int j = 0; j < currLen; ++j)
            {
                var w = words[j];
                for (int k = 0; k <= w.Length; ++k)
                {
                    var nstr = w.Insert(k, chars[i].ToString());
                    if (k == 0)
                        words[j] = nstr;
                    else
                        words.Add(nstr);
                }
            }
        }
        return words;
    }

Answer 27

반복적인 Java 구현이 있습니다. Uncommons수학 (객체 목록에서 작동):

/**
 * Generate the indices into the elements array for the next permutation. The
 * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its 
 * Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284)
 */
private void generateNextPermutationIndices()
{
    if (remainingPermutations == 0)
    {
        throw new IllegalStateException("There are no permutations " +
             "remaining. Generator must be reset to continue using.");
    }
    else if (remainingPermutations < totalPermutations)
    {
        // Find largest index j with 
        // permutationIndices[j] < permutationIndices[j + 1]
        int j = permutationIndices.length - 2;
        while (permutationIndices[j] > permutationIndices[j + 1])
        {
            j--;
        }

        // Find index k such that permutationIndices[k] is smallest integer 
        // greater than permutationIndices[j] to the right
        // of permutationIndices[j].
        int k = permutationIndices.length - 1;
        while (permutationIndices[j] > permutationIndices[k])
        {
            k--;
        }

        // Interchange permutation indices.
        int temp = permutationIndices[k];
        permutationIndices[k] = permutationIndices[j];
        permutationIndices[j] = temp;

        // Put tail end of permutation after jth position in increasing order.
        int r = permutationIndices.length - 1;
        int s = j + 1;

        while (r > s)
        {
            temp = permutationIndices[s];
            permutationIndices[s] = permutationIndices[r];
            permutationIndices[r] = temp;
            r--;
            s++;
        }
    }
    --remainingPermutations;
}

/**
 * Generate the next permutation and return a list containing
 * the elements in the appropriate order.  This overloaded method
 * allows the caller to provide a list that will be used and returned.
 * The purpose of this is to improve performance when iterating over
 * permutations.  If the {@link #nextPermutationAsList()} method is
 * used it will create a new list every time.  When iterating over
 * permutations this will result in lots of short-lived objects that
 * have to be garbage collected.  This method allows a single list
 * instance to be reused in such circumstances.
 * @param destination Provides a list to use to create the
 * permutation.  This is the list that will be returned, once
 * it has been filled with the elements in the appropriate order.
 * @return The next permutation as a list.
 */
public List<T> nextPermutationAsList(List<T> destination)
{
    generateNextPermutationIndices();
    // Generate actual permutation.
    destination.clear();
    for (int i : permutationIndices)
    {
        destination.add(elements[i]);
    }
    return destination;
}

전체 소스

Answer 28

def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
    list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list 

def func( x,i,j ): #returns x[i..j]
z = '' 
for i in range(i,j+1):
    z = z+x[i]
return z 

def perm( x , length , list ): #perm function
if length == 1 : # base case
    list.append( x[len(x)-1] )
    return list 
else:
    lists = perm( x , length-1 ,list )
    lists_temp = lists #temporarily storing the list 
    lists = []
    for i in range( len(lists_temp) ) :
        list_temp = gen(lists_temp[i],x[length-2],lists)
        lists += list_temp 
    return lists

Answer 29

def permutation(str)
  posibilities = []
  str.split('').each do |char|
    if posibilities.size == 0
      posibilities[0] = char.downcase
      posibilities[1] = char.upcase
    else
      posibilities_count = posibilities.length
      posibilities = posibilities + posibilities
      posibilities_count.times do |i|
        posibilities[i] += char.downcase
        posibilities[i+posibilities_count] += char.upcase
      end
    end
  end
  posibilities
end

비재귀 버전에 대한 내 의견은 다음과 같습니다.

Answer 30

파이썬적인 솔루션:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]