문자열/정수의 모든 순열을 나열합니다
https://stackoverflow.com/questions/756055
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
인터뷰를 프로그래밍하는 일반적인 작업 (인터뷰 경험이 아닌)은 현악기 또는 정수를 취하고 가능한 모든 순열을 나열하는 것입니다.
이것이 어떻게 이루어지고 그러한 문제를 해결하는 논리의 예가 있습니까?
나는 몇 개의 코드 스 니펫을 보았지만 잘 댓글을 달거나 설명하지 않았으므로 따르기가 어렵습니다.
해결책
우선 : 냄새가납니다 재귀 물론이야!
당신은 또한 원칙을 알고 싶었 기 때문에 인간 언어를 설명하기 위해 최선을 다했습니다. 재귀는 대부분의 시간이 매우 쉽다고 생각합니다. 두 단계 만 파악하면됩니다.
- 첫 번째 단계
- 다른 모든 단계 (모두 같은 논리가 있음)
~ 안에 인간 언어:
요컨대 :
1. 1 요소의 순열은 하나의 요소입니다.
2. 요소 세트의 순열은 각 요소의 목록이며, 다른 요소의 모든 순열과 관련이 있습니다.예시:
세트에 하나의 요소가있는 경우 ->
반환.
파마 (a) -> a세트에 두 문자가있는 경우 : 각 요소에 대해 : 다음과 같이 추가 된 나머지 요소의 순열로 요소를 반환하십시오.
Perm (ab) ->
a + perm (b) -> AB
b + perm (a) -> 바
추가 : 세트의 각 캐릭터에 대해 : 캐릭터를 반환,> 나머지 세트의 퍼머션으로 연결됩니다.
Perm (ABC) ->
a + perm (bc) -> 알파벳, ACB
b + perm (ac) -> BAC, BCA
c + perm (ab) -> 택시, CBA
Perm (ABC ... Z) ->
a + perm (...), b + perm (....)
....
나는 찾았다 의사 코드 ~에 http://www.programmersheeaven.com/mb/algorithms/369713/369713/permutation-algorithm-help/:
makePermutations(permutation) {
if (length permutation < required length) {
for (i = min digit to max digit) {
if (i not in permutation) {
makePermutations(permutation+i)
}
}
}
else {
add permutation to list
}
}
씨#
좋아, 그리고 더 정교한 것이 있고 http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : 다소 길지만 어쨌든 복사하기로 결정 했으므로 게시물은 원본에 의존하지 않습니다.
이 함수는 일련의 문자열을 취하고 정확한 문자열의 가능한 모든 순열을 기록합니다. 예를 들어 "ABC"가 제공된 경우 다음과 같습니다.
ABC, ACB, BAC, BCA, CAB, CBA.
암호:
class Program
{
private static void Swap(ref char a, ref char b)
{
if (a == b) return;
var temp = a;
a = b;
b = temp;
}
public static void GetPer(char[] list)
{
int x = list.Length - 1;
GetPer(list, 0, x);
}
private static void GetPer(char[] list, int k, int m)
{
if (k == m)
{
Console.Write(list);
}
else
for (int i = k; i <= m; i++)
{
Swap(ref list[k], ref list[i]);
GetPer(list, k + 1, m);
Swap(ref list[k], ref list[i]);
}
}
static void Main()
{
string str = "sagiv";
char[] arr = str.ToCharArray();
GetPer(arr);
}
}
다른 팁
LINQ를 사용할 수있는 경우 두 줄의 코드 일뿐입니다. 내 대답을 참조하십시오 여기.
편집하다
다음은 T의 목록에서 모든 순열 (조합이 아님)을 반환 할 수있는 일반적인 기능입니다.
static IEnumerable<IEnumerable<T>>
GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(e => !t.Contains(e)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
예시:
IEnumerable<IEnumerable<int>> result =
GetPermutations(Enumerable.Range(1, 3), 3);
출력 - 정수 목록 :
{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}
이 기능은 LINQ를 사용하므로 .NET 3.5 이상이 필요합니다.
여기서 솔루션을 찾았습니다. Java로 작성되었지만 C#으로 변환했습니다. 도움이되기를 바랍니다.
C#의 코드는 다음과 같습니다.
static void Main(string[] args)
{
string str = "ABC";
char[] charArry = str.ToCharArray();
permute(charArry, 0, 2);
Console.ReadKey();
}
static void permute(char[] arry, int i, int n)
{
int j;
if (i==n)
Console.WriteLine(arry);
else
{
for(j = i; j <=n; j++)
{
swap(ref arry[i],ref arry[j]);
permute(arry,i+1,n);
swap(ref arry[i], ref arry[j]); //backtrack
}
}
}
static void swap(ref char a, ref char b)
{
char tmp;
tmp = a;
a=b;
b = tmp;
}
재귀 필요가 없습니다, 여기 이 솔루션에 대한 좋은 정보입니다.
var values1 = new[] { 1, 2, 3, 4, 5 };
foreach (var permutation in values1.GetPermutations())
{
Console.WriteLine(string.Join(", ", permutation));
}
var values2 = new[] { 'a', 'b', 'c', 'd', 'e' };
foreach (var permutation in values2.GetPermutations())
{
Console.WriteLine(string.Join(", ", permutation));
}
Console.ReadLine();
나는이 알고리즘을 몇 년 동안 사용했는데 켜짐) 시각 그리고 우주 각각을 계산하기위한 복잡성 순열.
public static class SomeExtensions
{
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
{
var array = enumerable as T[] ?? enumerable.ToArray();
var factorials = Enumerable.Range(0, array.Length + 1)
.Select(Factorial)
.ToArray();
for (var i = 0L; i < factorials[array.Length]; i++)
{
var sequence = GenerateSequence(i, array.Length - 1, factorials);
yield return GeneratePermutation(array, sequence);
}
}
private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
{
var clone = (T[]) array.Clone();
for (int i = 0; i < clone.Length - 1; i++)
{
Swap(ref clone[i], ref clone[i + sequence[i]]);
}
return clone;
}
private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
{
var sequence = new int[size];
for (var j = 0; j < sequence.Length; j++)
{
var facto = factorials[sequence.Length - j];
sequence[j] = (int)(number / facto);
number = (int)(number % facto);
}
return sequence;
}
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
private static long Factorial(int n)
{
long result = n;
for (int i = 1; i < n; i++)
{
result = result * i;
}
return result;
}
}
void permute (char *str, int ptr) {
int i, len;
len = strlen(str);
if (ptr == len) {
printf ("%s\n", str);
return;
}
for (i = ptr ; i < len ; i++) {
swap (&str[ptr], &str[i]);
permute (str, ptr + 1);
swap (&str[ptr], &str[i]);
}
}
스왑 함수를 작성하여 문자 교체 할 수 있습니다.
이것은 순열 (string, 0)이라고합니다.
우선, 세트에는 문자열이나 정수가 아닌 순열이 있으므로 "문자열의 문자 세트"를 의미한다고 가정합니다.
크기 N 세트에는 n이 있습니다! n- 결연.
k = 1 ... n으로 호출되는 다음 의사 코드 (위키 백과)! 모든 순열을 제공합니다.
function permutation(k, s) {
for j = 2 to length(s) {
swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
k := k / j; // integer division cuts off the remainder
}
return s;
}
다음은 동등한 Python 코드 (0 기반 배열 인덱스의 경우)는 다음과 같습니다.
def permutation(k, s):
r = s[:]
for j in range(2, len(s)+1):
r[j-1], r[k%j] = r[k%j], r[j-1]
k = k/j+1
return r
C#의 약간 수정 된 버전은 모든 유형의 배열에서 순열이 필요합니다.
// USAGE: create an array of any type, and call Permutations()
var vals = new[] {"a", "bb", "ccc"};
foreach (var v in Permutations(vals))
Console.WriteLine(string.Join(",", v)); // Print values separated by comma
public static IEnumerable<T[]> Permutations<T>(T[] values, int fromInd = 0)
{
if (fromInd + 1 == values.Length)
yield return values;
else
{
foreach (var v in Permutations(values, fromInd + 1))
yield return v;
for (var i = fromInd + 1; i < values.Length; i++)
{
SwapValues(values, fromInd, i);
foreach (var v in Permutations(values, fromInd + 1))
yield return v;
SwapValues(values, fromInd, i);
}
}
}
private static void SwapValues<T>(T[] values, int pos1, int pos2)
{
if (pos1 != pos2)
{
T tmp = values[pos1];
values[pos1] = values[pos2];
values[pos2] = tmp;
}
}
좋아 했어요 fbryant87 간단하기 때문에 접근합니다. 불행히도, 그것은 다른 많은 "솔루션"과 마찬가지로 모든 순열을 제공하지 않거나 예를 들어 정수를 두 번 이상 포함하는 경우 정수를 제공합니다. 656123을 예로 들어 보겠습니다. 라인 :
var tail = chars.Except(new List<char>(){c});
제외하면 모든 발생이 제거됩니다, 즉 C = 6, 두 자리가 제거되고 우리는 EG 5123이 남아 있습니다. fbryant87기본 코드. 이것이 제가 생각해 낸 것입니다.
private static List<string> FindPermutations(string set)
{
var output = new List<string>();
if (set.Length == 1)
{
output.Add(set);
}
else
{
foreach (var c in set)
{
// Remove one occurrence of the char (not all)
var tail = set.Remove(set.IndexOf(c), 1);
foreach (var tailPerms in FindPermutations(tail))
{
output.Add(c + tailPerms);
}
}
}
return output;
}
.remove 및 .indexof를 사용하여 처음 발견 된 발생을 제거합니다. 적어도 내 사용을 위해 의도 된대로 작동하는 것 같습니다. 나는 그것이 더 영리해질 수 있다고 확신합니다.
그래도 한 가지 주목할 사항 : 결과 목록에는 복제물이 포함될 수 있으므로 메소드 리턴을 대신 해시 세트로 반환하거나 원하는 메소드를 사용하여 반환 후 복제물을 제거하십시오.
다음은 다음 순열을 찾을 수있는 모든 순열을 찾기위한 세 가지 알고리즘을 다루는 좋은 기사입니다.
http://www.cut-the-knot.org/do_you_know/allperm.shtml
C ++ 및 Python에는 내장되어 있습니다 next_permutation 그리고 itertools.permutations 각각 기능.
순전히 기능적인 F# 구현은 다음과 같습니다.
let factorial i =
let rec fact n x =
match n with
| 0 -> 1
| 1 -> x
| _ -> fact (n-1) (x*n)
fact i 1
let swap (arr:'a array) i j = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]
let rec permutation (k:int,j:int) (r:'a array) =
if j = (r.Length + 1) then r
else permutation (k/j+1, j+1) (swap r (j-1) (k%j))
let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source }
CLR 어레이의 변이 가능한 특성을 활용하기 위해 스왑을 변경함으로써 성능을 크게 향상시킬 수 있지만,이 구현은 소스 배열과 관련하여 스레드 안전하며 일부 상황에서는 바람직 할 수 있습니다. 또한, 16 개 이상의 요소가있는 배열의 경우 int가 int32 오버플로를 초래하기 때문에 int가 더 큰/임의 정밀도가있는 유형으로 교체해야합니다.
다음은 재귀를 사용하여 C#의 간단한 솔루션입니다.
void Main()
{
string word = "abc";
WordPermuatation("",word);
}
void WordPermuatation(string prefix, string word)
{
int n = word.Length;
if (n == 0) { Console.WriteLine(prefix); }
else
{
for (int i = 0; i < n; i++)
{
WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1)));
}
}
}
다음은 문자열과 정수 모두 입력으로 이해하기 쉬운 순열 기능입니다. 이것으로 출력 길이를 설정할 수도 있습니다(정상적인 경우 입력 길이와 같음)
끈
static ICollection<string> result;
public static ICollection<string> GetAllPermutations(string str, int outputLength)
{
result = new List<string>();
MakePermutations(str.ToCharArray(), string.Empty, outputLength);
return result;
}
private static void MakePermutations(
char[] possibleArray,//all chars extracted from input
string permutation,
int outputLength//the length of output)
{
if (permutation.Length < outputLength)
{
for (int i = 0; i < possibleArray.Length; i++)
{
var tempList = possibleArray.ToList<char>();
tempList.RemoveAt(i);
MakePermutations(tempList.ToArray(),
string.Concat(permutation, possibleArray[i]), outputLength);
}
}
else if (!result.Contains(permutation))
result.Add(permutation);
}
그리고 정수 발신자 메소드를 변경하십시오 makepermutations () 손대지 않은 채로 남아 있습니다.
public static ICollection<int> GetAllPermutations(int input, int outputLength)
{
result = new List<string>();
MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength);
return result.Select(m => int.Parse(m)).ToList<int>();
}
예 1 : getAllPerMutations ( "ABC", 3); "ABC" "ACB" "BAC" "BCA" "CAB" "CBA"
예 2 : getAllPerMutations ( "ABCD", 2); "AB" "AC" "AD" "BA" "BC" "BD" "CA" "CB" "CD" "DA" "DB" "DC"
예 3 : GetAllPermutations (486,2); 48 46 84 86 64 68
class Program
{
public static void Main(string[] args)
{
Permutation("abc");
}
static void Permutation(string rest, string prefix = "")
{
if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);
// Each letter has a chance to be permutated
for (int i = 0; i < rest.Length; i++)
{
Permutation(rest.Remove(i, 1), prefix + rest[i]);
}
}
}
다음은 모든 순열을 인쇄하는 기능입니다. 이 기능은 Peter가 설명한 논리를 구현합니다.
public class Permutation
{
//http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm
public static void permuteString(String beginningString, String endingString)
{
if (endingString.Length <= 1)
Console.WriteLine(beginningString + endingString);
else
for (int i = 0; i < endingString.Length; i++)
{
String newString = endingString.Substring(0, i) + endingString.Substring(i + 1);
permuteString(beginningString + endingString.ElementAt(i), newString);
}
}
}
static void Main(string[] args)
{
Permutation.permuteString(String.Empty, "abc");
Console.ReadLine();
}
아래는 순열의 구현입니다. 내가 재미를 위해하고 있었던 것처럼 변수 이름을 신경 쓰지 마세요 :)
class combinations
{
static void Main()
{
string choice = "y";
do
{
try
{
Console.WriteLine("Enter word :");
string abc = Console.ReadLine().ToString();
Console.WriteLine("Combinatins for word :");
List<string> final = comb(abc);
int count = 1;
foreach (string s in final)
{
Console.WriteLine("{0} --> {1}", count++, s);
}
Console.WriteLine("Do you wish to continue(y/n)?");
choice = Console.ReadLine().ToString();
}
catch (Exception exc)
{
Console.WriteLine(exc);
}
} while (choice == "y" || choice == "Y");
}
static string swap(string test)
{
return swap(0, 1, test);
}
static List<string> comb(string test)
{
List<string> sec = new List<string>();
List<string> first = new List<string>();
if (test.Length == 1) first.Add(test);
else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
else if (test.Length > 2)
{
sec = generateWords(test);
foreach (string s in sec)
{
string init = s.Substring(0, 1);
string restOfbody = s.Substring(1, s.Length - 1);
List<string> third = comb(restOfbody);
foreach (string s1 in third)
{
if (!first.Contains(init + s1)) first.Add(init + s1);
}
}
}
return first;
}
static string ShiftBack(string abc)
{
char[] arr = abc.ToCharArray();
char temp = arr[0];
string wrd = string.Empty;
for (int i = 1; i < arr.Length; i++)
{
wrd += arr[i];
}
wrd += temp;
return wrd;
}
static List<string> generateWords(string test)
{
List<string> final = new List<string>();
if (test.Length == 1)
final.Add(test);
else
{
final.Add(test);
string holdString = test;
while (final.Count < test.Length)
{
holdString = ShiftBack(holdString);
final.Add(holdString);
}
}
return final;
}
static string swap(int currentPosition, int targetPosition, string temp)
{
char[] arr = temp.ToCharArray();
char t = arr[currentPosition];
arr[currentPosition] = arr[targetPosition];
arr[targetPosition] = t;
string word = string.Empty;
for (int i = 0; i < arr.Length; i++)
{
word += arr[i];
}
return word;
}
}
다음은 내가 쓴 높은 수준의 예입니다. 인간 언어 베드로가 준 설명 :
public List<string> FindPermutations(string input)
{
if (input.Length == 1)
return new List<string> { input };
var perms = new List<string>();
foreach (var c in input)
{
var others = input.Remove(input.IndexOf(c), 1);
perms.AddRange(FindPermutations(others).Select(perm => c + perm));
}
return perms;
}
성능과 메모리가 문제라면 매우 효율적인 구현을 제안합니다. 에 따르면 위키 백과의 힙 알고리즘, 그것은 가장 빠릅니다. 그것이 당신의 필요에 맞을 수 있기를 바랍니다 :-)!
이것을 10의 LINQ 구현과 비교하는 것처럼! (코드 포함) :
- 이것 : 235 millisecs의 36288000 항목
LINQ : 36288000 50051 millisecs의 항목
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Runtime.CompilerServices; using System.Text; namespace WpfPermutations { /// <summary> /// EO: 2016-04-14 /// Generator of all permutations of an array of anything. /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 /// </summary> public static class Permutations { /// <summary> /// Heap's algorithm to find all pmermutations. Non recursive, more efficient. /// </summary> /// <param name="items">Items to permute in each possible ways</param> /// <param name="funcExecuteAndTellIfShouldStop"></param> /// <returns>Return true if cancelled</returns> public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop) { int countOfItem = items.Length; if (countOfItem <= 1) { return funcExecuteAndTellIfShouldStop(items); } var indexes = new int[countOfItem]; for (int i = 0; i < countOfItem; i++) { indexes[i] = 0; } if (funcExecuteAndTellIfShouldStop(items)) { return true; } for (int i = 1; i < countOfItem;) { if (indexes[i] < i) { // On the web there is an implementation with a multiplication which should be less efficient. if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same. { Swap(ref items[i], ref items[indexes[i]]); } else { Swap(ref items[i], ref items[0]); } if (funcExecuteAndTellIfShouldStop(items)) { return true; } indexes[i]++; i = 1; } else { indexes[i++] = 0; } } return false; } /// <summary> /// This function is to show a linq way but is far less efficient /// </summary> /// <typeparam name="T"></typeparam> /// <param name="list"></param> /// <param name="length"></param> /// <returns></returns> static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length) { if (length == 1) return list.Select(t => new T[] { t }); return GetPermutations(list, length - 1) .SelectMany(t => list.Where(e => !t.Contains(e)), (t1, t2) => t1.Concat(new T[] { t2 })); } /// <summary> /// Swap 2 elements of same type /// </summary> /// <typeparam name="T"></typeparam> /// <param name="a"></param> /// <param name="b"></param> [MethodImpl(MethodImplOptions.AggressiveInlining)] static void Swap<T>(ref T a, ref T b) { T temp = a; a = b; b = temp; } /// <summary> /// Func to show how to call. It does a little test for an array of 4 items. /// </summary> public static void Test() { ForAllPermutation("123".ToCharArray(), (vals) => { Debug.Print(String.Join("", vals)); return false; }); int[] values = new int[] { 0, 1, 2, 4 }; Debug.Print("Non Linq"); ForAllPermutation(values, (vals) => { Debug.Print(String.Join("", vals)); return false; }); Debug.Print("Linq"); foreach(var v in GetPermutations(values, values.Length)) { Debug.Print(String.Join("", v)); } // Performance int count = 0; values = new int[10]; for(int n = 0; n < values.Length; n++) { values[n] = n; } Stopwatch stopWatch = new Stopwatch(); stopWatch.Reset(); stopWatch.Start(); ForAllPermutation(values, (vals) => { foreach(var v in vals) { count++; } return false; }); stopWatch.Stop(); Debug.Print($"Non Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); count = 0; stopWatch.Reset(); stopWatch.Start(); foreach (var vals in GetPermutations(values, values.Length)) { foreach (var v in vals) { count++; } } stopWatch.Stop(); Debug.Print($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); } } }
JavaScript (Nodejs)의 내 솔루션은 다음과 같습니다. 주요 아이디어는 한 번에 하나의 요소를 사용하여 문자열에서 "제거"하고 나머지 문자를 변경하고 전면에 요소를 삽입한다는 것입니다.
function perms (string) {
if (string.length == 0) {
return [];
}
if (string.length == 1) {
return [string];
}
var list = [];
for(var i = 0; i < string.length; i++) {
var invariant = string[i];
var rest = string.substr(0, i) + string.substr(i + 1);
var newPerms = perms(rest);
for (var j = 0; j < newPerms.length; j++) {
list.push(invariant + newPerms[j]);
}
}
return list;
}
module.exports = perms;
그리고 테스트는 다음과 같습니다.
require('should');
var permutations = require('../src/perms');
describe('permutations', function () {
it('should permute ""', function () {
permutations('').should.eql([]);
})
it('should permute "1"', function () {
permutations('1').should.eql(['1']);
})
it('should permute "12"', function () {
permutations('12').should.eql(['12', '21']);
})
it('should permute "123"', function () {
var expected = ['123', '132', '321', '213', '231', '312'];
var actual = permutations('123');
expected.forEach(function (e) {
actual.should.containEql(e);
})
})
it('should permute "1234"', function () {
// Wolfram Alpha FTW!
var expected = ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132'];
var actual = permutations('1234');
expected.forEach(function (e) {
actual.should.containEql(e);
})
})
})
내가 생각할 수있는 가장 간단한 솔루션은 다음과 같습니다.
let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs
그만큼 distribute 함수는 새로운 요소를 취합니다 e 그리고 n-요소 목록과 목록을 반환합니다 n+1 각각이 목록에 있습니다 e 다른 장소에 삽입되었습니다. 예를 들어 삽입 10 목록에있는 4 개의 가능한 장소 각각에서 [1;2;3]:
> distribute 10 [1..3];;
val it : int list list =
[[10; 1; 2; 3]; [1; 10; 2; 3]; [1; 2; 10; 3]; [1; 2; 3; 10]]
그만큼 permute 함수는 각 요소의 차례로 차례대로 배포되어 지금까지 축적 된 순열 위에 분포되어 모든 순열이 절정에 이릅니다. 예를 들어, 목록의 6 가지 순열 [1;2;3]:
> permute [1;2;3];;
val it : int list list =
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]
변경 fold a scan 중간체 축적기를 유지하기 위해 한 번에 한 번에 요소를 생성하는 방법에 대해 약간의 조명을 흘립니다.
> Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];;
val it : seq<int list list> =
seq
[[[]]; [[1]]; [[2; 1]; [1; 2]];
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]]
문자열의 순열을 나열합니다. 문자가 반복 될 때 중복을 피하십시오.
using System;
using System.Collections;
class Permutation{
static IEnumerable Permutations(string word){
if (word == null || word.Length <= 1) {
yield return word;
yield break;
}
char firstChar = word[0];
foreach( string subPermute in Permutations (word.Substring (1)) ) {
int indexOfFirstChar = subPermute.IndexOf (firstChar);
if (indexOfFirstChar == -1) indexOfFirstChar = subPermute.Length;
for( int index = 0; index <= indexOfFirstChar; index++ )
yield return subPermute.Insert (index, new string (firstChar, 1));
}
}
static void Main(){
foreach( var permutation in Permutations ("aab") )
Console.WriteLine (permutation);
}
}
다음은 모든 순열을 재귀 적으로 인쇄하는 기능입니다.
public void Permutations(string input, StringBuilder sb)
{
if (sb.Length == input.Length)
{
Console.WriteLine(sb.ToString());
return;
}
char[] inChar = input.ToCharArray();
for (int i = 0; i < input.Length; i++)
{
if (!sb.ToString().Contains(inChar[i]))
{
sb.Append(inChar[i]);
Permutations(input, sb);
RemoveChar(sb, inChar[i]);
}
}
}
private bool RemoveChar(StringBuilder input, char toRemove)
{
int index = input.ToString().IndexOf(toRemove);
if (index >= 0)
{
input.Remove(index, 1);
return true;
}
return false;
}
class Permutation
{
public static List<string> Permutate(string seed, List<string> lstsList)
{
loopCounter = 0;
// string s="\w{0,2}";
var lstStrs = PermuateRecursive(seed);
Trace.WriteLine("Loop counter :" + loopCounter);
return lstStrs;
}
// Recursive function to find permutation
private static List<string> PermuateRecursive(string seed)
{
List<string> lstStrs = new List<string>();
if (seed.Length > 2)
{
for (int i = 0; i < seed.Length; i++)
{
str = Swap(seed, 0, i);
PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach(
s =>
{
lstStrs.Add(str[0] + s);
loopCounter++;
});
;
}
}
else
{
lstStrs.Add(seed);
lstStrs.Add(Swap(seed, 0, 1));
}
return lstStrs;
}
//Loop counter variable to count total number of loop execution in various functions
private static int loopCounter = 0;
//Non recursive version of permuation function
public static List<string> Permutate(string seed)
{
loopCounter = 0;
List<string> strList = new List<string>();
strList.Add(seed);
for (int i = 0; i < seed.Length; i++)
{
int count = strList.Count;
for (int j = i + 1; j < seed.Length; j++)
{
for (int k = 0; k < count; k++)
{
strList.Add(Swap(strList[k], i, j));
loopCounter++;
}
}
}
Trace.WriteLine("Loop counter :" + loopCounter);
return strList;
}
private static string Swap(string seed, int p, int p2)
{
Char[] chars = seed.ToCharArray();
char temp = chars[p2];
chars[p2] = chars[p];
chars[p] = temp;
return new string(chars);
}
}
다음은 약간 단순화 된 C# 답변입니다.
public static void StringPermutationsDemo()
{
strBldr = new StringBuilder();
string result = Permute("ABCD".ToCharArray(), 0);
MessageBox.Show(result);
}
static string Permute(char[] elementsList, int startIndex)
{
if (startIndex == elementsList.Length)
{
foreach (char element in elementsList)
{
strBldr.Append(" " + element);
}
strBldr.AppendLine("");
}
else
{
for (int tempIndex = startIndex; tempIndex <= elementsList.Length - 1; tempIndex++)
{
Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
Permute(elementsList, (startIndex + 1));
Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
}
}
return strBldr.ToString();
}
static void Swap(ref char Char1, ref char Char2)
{
char tempElement = Char1;
Char1 = Char2;
Char2 = tempElement;
}
산출:
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
이것은 내가 이해하기 쉬운 나의 해결책입니다
class ClassicPermutationProblem
{
ClassicPermutationProblem() { }
private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position)
{
foreach (T element in list)
{
List<T> currentTemp = temp.ToList();
if (!currentTemp.Contains(element))
currentTemp.Add(element);
else
continue;
if (position == list.Count)
finalList.Add(currentTemp);
else
PopulatePosition(finalList, list, currentTemp, position + 1);
}
}
public static List<List<int>> GetPermutations(List<int> list)
{
List<List<int>> results = new List<List<int>>();
PopulatePosition(results, list, new List<int>(), 1);
return results;
}
}
static void Main(string[] args)
{
List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 });
}
다음은 언급 된 알고의 더 구현입니다.
public class Program
{
public static void Main(string[] args)
{
string str = "abcefgh";
var astr = new Permutation().GenerateFor(str);
Console.WriteLine(astr.Length);
foreach(var a in astr)
{
Console.WriteLine(a);
}
//a.ForEach(Console.WriteLine);
}
}
class Permutation
{
public string[] GenerateFor(string s)
{
if(s.Length == 1)
{
return new []{s};
}
else if(s.Length == 2)
{
return new []{s[1].ToString()+s[0].ToString(),s[0].ToString()+s[1].ToString()};
}
var comb = new List<string>();
foreach(var c in s)
{
string cStr = c.ToString();
var sToProcess = s.Replace(cStr,"");
if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0)
{
var conCatStr = GenerateFor(sToProcess);
foreach(var a in conCatStr)
{
comb.Add(c.ToString()+a);
}
}
}
return comb.ToArray();
}
}
//Generic C# Method
private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
{
var perms = new List<T[]>();
var l = input.Length - 1;
if (l == startIndex)
perms.Add(input);
else
{
for (int i = startIndex; i <= l; i++)
{
var copy = input.ToArray(); //make copy
var temp = copy[startIndex];
copy[startIndex] = copy[i];
copy[i] = temp;
perms.AddRange(GetPerms(copy, startIndex + 1));
}
}
return perms;
}
//usages
char[] charArray = new char[] { 'A', 'B', 'C' };
var charPerms = GetPerms(charArray);
string[] stringArray = new string[] { "Orange", "Mango", "Apple" };
var stringPerms = GetPerms(stringArray);
int[] intArray = new int[] { 1, 2, 3 };
var intPerms = GetPerms(intArray);
/// <summary>
/// Print All the Permutations.
/// </summary>
/// <param name="inputStr">input string</param>
/// <param name="strLength">length of the string</param>
/// <param name="outputStr">output string</param>
private void PrintAllPermutations(string inputStr, int strLength,string outputStr, int NumberOfChars)
{
//Means you have completed a permutation.
if (outputStr.Length == NumberOfChars)
{
Console.WriteLine(outputStr);
return;
}
//For loop is used to print permutations starting with every character. first print all the permutations starting with a,then b, etc.
for(int i=0 ; i< strLength; i++)
{
// Recursive call : for a string abc = a + perm(bc). b+ perm(ac) etc.
PrintAllPermutations(inputStr.Remove(i, 1), strLength - 1, outputStr + inputStr.Substring(i, 1), 4);
}
}
제휴하지 않습니다 StackOverflow
