문자열의 가능한 모든 순열 목록 생성
x자와 y자 사이의 문자열에서 가능한 모든 순열 목록을 생성하려면 어떻게 해야 하며, 여기에는 다양한 문자 목록이 포함됩니다.
어떤 언어라도 가능하지만, 휴대가 가능해야 합니다.
이렇게 하는 방법에는 여러 가지가 있습니다.일반적인 방법은 재귀, 메모라이제이션 또는 동적 프로그래밍을 사용합니다.기본 개념은 길이 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) 항목이 됩니다.
역추적을 이용하는 것이 좋습니다.
#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;
}
당신은 많은 조건을 달게 될 겁니다, 그건 분명...
여기서 x와 y는 사용자가 정의하는 방법이고 r은 사용자가 올바르게 이해하고 있는 경우 선택하는 문자의 수입니다.필요에 따라 반드시 이것들을 생성해야 하며 엉성해지지 말고 파워셋을 생성한 다음 문자열의 길이를 필터링해야 합니다.
다음과 같은 것들은 분명히 이것들을 생성하는 최선의 방법은 아니지만, 그것은 흥미로운 것이며, 그렇다고 할 수도 없습니다.
2,)-조합이과 함께 한. - )-으로, (s,t)-조합은 Knuth (4, 2, 7.2.1.3)-조합은 Knuth (은4, 2를, 의7.2.1.3)-조합과 같습니다. - (s,t)-조합은 Knuth에 의해 사용됩니다.는 먼저 형태로 하고 ( (t)) 를 세어 수 . 우리는 먼저 이진 형태로 각각 (s,t)-조합을 생성하고 (따라서, 길이 (s+t)) 각각의 1의 왼쪽에 있는 0의 개수를 세어 이를 알아낼 수 있습니다.
10001000011101 -->는 순열이 됩니다: {0, 3, 4, 4, 4, 1}
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)
원하는 작업의 일부를 수행하는 알고리즘을 설명하는 "집합의 부분집합을 효율적으로 열거"에서 길이 x부터 y까지의 N자의 모든 부분집합을 빠르게 생성할 수 있습니다.이것은 C에 구현된 것을 포함하고 있습니다.
각 부분 집합에 대해서는 모든 순열을 생성해야 합니다.예를 들어, 만약 당신이 "abcde"에서 3자를 원한다면, 이 알고리즘은 당신에게 "abc", "abd", "abe"... 하지만 당신은 "acb", "bac", "bca" 등을 얻기 위해 각각의 문자를 순열해야 합니다.
Sarp의 답변을 기반으로 작동하는 자바 코드:
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);
}
}
여기 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;
}
}
여기에 좋은 답이 많이 있습니다.저는 또한 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;
});
}
참고: 반복되는 문자가 있는 문자열은 고유한 순열을 생성하지 않습니다.
루비에서 이것을 재빨리 휘둘러보았습니다.
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 임계값 미만인 것을 모두 제거하고 결과를 반환합니다.
잠재적으로 무의미한 입력(null 문자 목록, x와 y의 이상한 값 등)으로 테스트하지 않았습니다.
이것은 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)))))
간단한 단어 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);
... 여기 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;
}
퍼뮤트(ABC) -> A.perm(BC) -> A.perm[B.perm(C) -> A.perm[(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)] 각 알파벳을 삽입할 때 중복을 제거하려면 이전 문자열이 같은 알파벳으로 끝나는지 확인합니다(왜? -exercise).
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;
}
모든 순열 및 중복 인쇄
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;
}
}
}
Perl에서 소문자로 제한하려면 다음을 수행할 수 있습니다.
my @result = ("a" .. "zzzz");
이것은 소문자를 사용하여 가능한 모든 문자열을 1자에서 4자 사이에 제공합니다.의우경으로 바꿉니다."a""A"그리고."zzzz""ZZZZ".
혼합된 경우에는 훨씬 더 어려워지기 때문에 Perl의 기본 제공 운영자 중 하나에서는 그렇게 할 수 없을 것입니다.
효과가 있는 루비 답변:
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")
다음 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!(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()));
}
}
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;
}
}
저는 당신이 왜 처음부터 이것을 하려고 하는지 잘 모르겠습니다.x와 y의 중간 크기 값에 대한 결과 집합은 커지며 x 및/또는 y가 커짐에 따라 기하급수적으로 커집니다.
가능한 문자 집합을 알파벳의 소문자 26개라고 가정하고, 응용 프로그램에 길이 = 5인 모든 순열을 생성하도록 요청합니다. 메모리가 부족하지 않다고 가정하면 11,881,376개의 문자열을 반환합니다.그 길이를 6까지 늘리면 308,915,776개의 끈을 돌려받을 수 있습니다.이 숫자들은 고통스러울 정도로 매우 빠르게 증가합니다.
이것이 제가 자바로 정리한 해결책입니다.두 개의 런타임 인수(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);
}
}
}
}
여기 제가 생각해낸 자바스크립트로 된 비재귀 버전이 있습니다.위의 Knuth의 non-recursive one을 기반으로 한 것은 아니지만, 요소 스와핑에서 몇 가지 유사점이 있습니다.최대 8개 요소의 입력 배열에 대한 정확성을 확인했습니다.
신속한 최적화는 비행 전에out 및 열및피피및열push().
기본 아이디어는 다음과 같습니다.
단일 소스 배열이 주어지면 첫 번째 새로운 배열 집합을 생성하여 첫 번째 요소를 각 후속 요소와 차례로 스왑하고, 매번 다른 요소를 방해받지 않게 합니다.예: 1234가 주어지면 1234, 2134, 3214, 4231을 생성합니다.
이전 패스의 각 배열을 새 패스의 시드로 사용하되, 첫 번째 요소를 스왑하는 대신 두 번째 요소를 각 후속 요소와 스왑합니다.또한, 이번에는 원래 배열을 출력에 포함시키지 마십시오.
완료될 때까지 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;
}
루비색:
str = "a"
100_000_000.times {puts str.next!}
꽤 빠르지만 시간이 좀 걸릴 것 같습니다 =).물론, 짧은 줄이 흥미롭지 않다면 "아아아아아"부터 시작할 수 있습니다.
하지만 실제 질문을 잘못 해석했을 수도 있습니다. 게시물 중 하나에서는 마치 단순한 문자열 라이브러리가 필요한 것처럼 들렸지만, 주요 질문에서는 특정 문자열을 순열해야 하는 것처럼 들립니다.
당신의 문제는 이것과 다소 비슷합니다: http://beust.com/weblog/archives/000491.html (어떤 숫자도 반복되지 않는 모든 정수를 나열하십시오. 이로 인해 많은 언어가 해결되었고, Ocaml 가이는 순열을 사용하고, 일부 자바 가이는 또 다른 해결책을 사용했습니다.)
저는 오늘 이것이 필요했고, 이미 주어진 답변들이 저를 올바른 방향으로 가리키고 있었지만, 그것들은 제가 원하는 것이 아니었습니다.
힙의 방법을 이용한 구현이 여기 있습니다.어레이의 길이는 최소 3 이상이어야 하며, 실제적인 고려 사항을 위해 인내심과 클럭 속도 등을 고려할 때 10 이상은 안 됩니다.
루프에 들어가기 전에 초기화합니다.Perm(1 To N)첫번째 순열로Stack(3 To N)0으로, 그리고Level와 함께2**. 루프콜이 끝날 때쯤NextPerm, 우리가 끝나면 거짓으로 돌아올 겁니다
* 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도 흥미로운 논문을 썼습니다.
다음은 문자열의 순열을 인쇄하는 방법을 설명하는 링크입니다.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
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()
이것이 당신에게 도움이 되기를 바랍니다.숫자 뿐만 아니라 모든 문자를 사용할 수 있습니다.
이전의 많은 답변들은 역추적을 사용했습니다.초기 정렬 후 순열을 생성하는 점근적으로 최적화된 O(n*n!) 방식입니다.
class Permutation {
/* runtime -O(n) for generating nextPermutaion
* and O(n*n!) for generating all n! permutations with increasing sorted array as start
* return true, if there exists next lexicographical sequence
* e.g [a,b,c],3-> true, modifies array to [a,c,b]
* e.g [c,b,a],3-> false, as it is largest lexicographic possible */
public static boolean nextPermutation(char[] seq, int len) {
// 1
if (len <= 1)
return false;// no more perm
// 2: Find last j such that seq[j] <= seq[j+1]. Terminate if no such j exists
int j = len - 2;
while (j >= 0 && seq[j] >= seq[j + 1]) {
--j;
}
if (j == -1)
return false;// no more perm
// 3: Find last l such that seq[j] <= seq[l], then exchange elements j and l
int l = len - 1;
while (seq[j] >= seq[l]) {
--l;
}
swap(seq, j, l);
// 4: Reverse elements j+1 ... count-1:
reverseSubArray(seq, j + 1, len - 1);
// return seq, add store next perm
return true;
}
private static void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void reverseSubArray(char[] a, int lo, int hi) {
while (lo < hi) {
swap(a, lo, hi);
++lo;
--hi;
}
}
public static void main(String[] args) {
String str = "abcdefg";
char[] array = str.toCharArray();
Arrays.sort(array);
int cnt=0;
do {
System.out.println(new String(array));
cnt++;
}while(nextPermutation(array, array.length));
System.out.println(cnt);//5040=7!
}
//if we use "bab"-> "abb", "bab", "bba", 3(#permutations)
}
재귀적 접근법
func StringPermutations(inputStr string) (permutations []string) {
for i := 0; i < len(inputStr); i++ {
inputStr = inputStr[1:] + inputStr[0:1]
if len(inputStr) <= 2 {
permutations = append(permutations, inputStr)
continue
}
leftPermutations := StringPermutations(inputStr[0 : len(inputStr)-1])
for _, leftPermutation := range leftPermutations {
permutations = append(permutations, leftPermutation+inputStr[len(inputStr)-1:])
}
}
return
}
이것이 여러분의 질문에 정확하게 답하지는 않지만, 여기에 같은 길이의 다수의 문자열로부터 글자의 순열을 모두 생성하는 한 가지 방법이 있습니다. 예를 들어, 만약 여러분의 단어가 "커피", "줌라" 그리고 "무들"이었다면, 여러분은 "coodle", "judee", "joffle" 등과 같은 출력을 기대할 수 있습니다.
기본적으로 조합 수는 (단어 수)의 거듭제곱에 대한 (단어 수)입니다.따라서 0과 조합 수 - 1 사이에서 임의의 숫자를 선택하고 그 숫자를 기본(단어 수)으로 변환한 다음 해당 숫자의 각 숫자를 다음 단어에서 가져올 지표로 사용합니다.
예: 위의 예에서.단어 3개, 글자 6개 = 729개 조합.임의의 숫자를 선택하세요: 465. 기본 3: 122020으로 전환하세요.단어 1에서 첫번째 글자, 단어 2에서 두번째 글자, 단어 2에서 세번째 글자, 단어 0에서 네번째 글자를...그러면..."joofle".
모든 순열을 원하신다면 0에서 728까지 순환하시면 됩니다.물론, 만약 여러분이 단지 하나의 임의의 값을 선택한다면, 많은
단순한 글자들을 뒤적이는 것이 덜 정확한 방법일 것입니다.이 방법을 사용하면 모든 순열을 원할 경우 재귀를 피할 수 있으며, 수학을 알고(tm) 있는 것처럼 보이게 해줍니다.
조합의 수가 과할 경우, 일련의 작은 단어로 나누어 마지막에 연결할 수 있습니다.
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;
}
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
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
이것은 비재귀적 버전에 대한 나의 의견입니다.
언급URL : https://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string
'programing' 카테고리의 다른 글
| 아직 존재하지 않는 InnoDB 행을 잠그려면 어떻게 해야 합니까? (0) | 2023.09.08 |
|---|---|
| 여러 열을 mysql의 고유 식별자로 사용 (0) | 2023.09.08 |
| Laravel - my Web services Api를 여러 번 호출하면 데이터베이스의 단일 항목과 데이터베이스의 복제 기록 논리를 무시합니다. (0) | 2023.09.08 |
| 함수(콜백)를 다른 함수의 인수로 사용하는 것은 파이썬에서 어떻게 작동합니까? (0) | 2023.09.08 |
| 엑셀 시트로 오늘 날짜를 어떻게 알 수 있습니까? (0) | 2023.09.08 |