c# - matematicos - Listado de todas las permutaciones de una cadena/entero

ejemplos de arreglos matematicos

Question

Una tarea común en la programación de entrevistas (aunque no por mi experiencia de entrevistas) es tomar una cadena o un número entero y enumerar cada permutación posible.

¿Hay un ejemplo de cómo se hace esto y la lógica detrás de la solución de ese problema?

He visto algunos fragmentos de código pero no fueron bien comentados / explicados y, por lo tanto, difíciles de seguir.

Answer 1

Aquí está la función que imprimirá todas las permutaciones recursivamente.

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;
}

Answer 2

Aquí está la función que imprimirá todo permutaion. Esta función implementa la lógica Explicada por 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();
}

Answer 3

Aquí está la solución más simple que puedo pensar:

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

La función de distribute toma un nuevo elemento e una lista de elementos n y devuelve una lista de n+1 listas, cada una de las cuales se ha insertado e en un lugar diferente. Por ejemplo, insertando 10 en cada uno de los cuatro lugares posibles en la lista [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]]

La función permute pliega sobre cada elemento distribuyéndose a lo largo de las permutaciones acumuladas hasta el momento, culminando en todas las permutaciones. Por ejemplo, las 6 permutaciones de la lista [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]]

Cambiar el fold a un scan para mantener los acumuladores intermedios arroja algo de luz sobre cómo se generan las permutaciones de un elemento a la vez:

> 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]]]

Answer 4

Aquí está mi solución en JavaScript (NodeJS). La idea principal es que tomamos un elemento a la vez, lo "removemos" de la cadena, variamos el resto de los caracteres e insertamos el elemento al frente.

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;

Y aquí están las pruebas:

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);
})
})
})

Answer 5

Aquí hay un buen artículo que cubre tres algoritmos para encontrar todas las permutaciones, incluida una para encontrar la siguiente permutación.

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

C ++ y Python tienen incorporadas funciones next_permutation e itertools.permutations respectivamente.

Answer 6

Aquí hay un ejemplo de alto nivel que escribí que ilustra la explicación del lenguaje humano que Pedro dio:

 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;
}

Answer 7

Aquí hay una función de permutación fácil de entender para la cadena y el entero como entrada. Con esto , incluso puede establecer su longitud de salida (que en el caso normal es igual a la longitud de entrada)

Cuerda

 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);
}

y para Entero simplemente cambia el método de llamador y MakePermutations () permanece intacto:

 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>();
}

ejemplo 1: GetAllPermutations ("abc", 3); "abc" "acb" "bac" "bca" "cab" "cba"

ejemplo 2: GetAllPermutations ("abcd", 2); "ab" "ac" "ad" "ba" "bc" "bd" "ca" "cb" "cd" "da" "db" "dc"

ejemplo 3: GetAllPermutations (486,2); 48 46 84 86 64 68

Answer 8

Aquí hay una implementación de F # puramente funcional:

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 }

El rendimiento puede mejorarse en gran medida cambiando el intercambio para aprovechar la naturaleza mutable de las matrices CLR, pero esta implementación es segura para subprocesos con respecto a la matriz fuente y puede ser deseable en algunos contextos. Además, para matrices con más de 16 elementos, int debe reemplazarse por tipos con mayor / arbitraria precisión, ya que factorial 17 da como resultado un desbordamiento de int32.

Answer 9

Aquí hay una implementación más del algo mencionado.

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();
}
}

Answer 10

Aquí hay una respuesta C # que está un poco simplificada.

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;
}

Salida:

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

Answer 11

Aquí hay una solución simple en c # usando la recursión,

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)));
}
}
}

Answer 12

Aquí he encontrado la solución. Fue escrito en Java, pero lo he convertido en C #. Espero que te ayude.

Aquí está el código en 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;
}

Answer 13

El siguiente es mi implementación de permutación. No me molestan los nombres de las variables, ya que lo estaba haciendo por diversión :)

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;
}
}

Answer 14

En primer lugar, ¡huele a recursión, por supuesto!

Como también querías saber el principio, hice todo lo posible por explicarle el lenguaje humano. Creo que la recursión es muy fácil la mayoría de las veces. Solo tiene que comprender dos pasos:

1. El primer paso
2. Todos los otros pasos (todos con la misma lógica)

En lenguaje humano :

En breve:
1. La permutación de 1 elemento es un elemento.
2. La permutación de un conjunto de elementos es una lista de cada uno de los elementos, concatenada con cada permutación de los otros elementos.

Ejemplo:

Si el conjunto solo tiene un elemento ->
devolverlo.
permanente (a) -> a

Si el conjunto tiene dos caracteres: para cada elemento en él: devuelve el elemento, con la permutación del resto de los elementos añadidos, así:

permanente (ab) ->

a + permanente (b) -> ab

b + permanente (a) -> ba

Además: para cada personaje en el conjunto: devuelve un carácter, concatenado con una perumación de> el resto del conjunto

permanente (abc) ->

a + permanente (bc) -> abc , acb

b + perm (ac) -> bac , bca

c + perm (ab) -> cab , cba

permanente (abc ... z) ->

a + permanente (...), b + permanente (....)
....

Encontré el pseudocódigo en http://www.programmersheaven.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
}
}

DO#

OK, y algo más elaborado (y dado que está etiquetado c #), de http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : bastante largo, pero decidí copiarlo De todas formas, la publicación no depende del original.

La función toma una cadena de caracteres, y anota cada permutación posible de esa cadena exacta, por lo que, por ejemplo, si se ha suministrado "ABC", debería derramarse:

ABC, ACB, BAC, BCA, CAB, CBA.

Código:

class Program
{
private static void Swap(ref char a, ref char b)
{
if (a == b) return;
a ^= b;
b ^= a;
a ^= b;
}
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);
}
}

Answer 15

En primer lugar, los conjuntos tienen permutaciones, no cadenas o números enteros, así que supongo que quieres decir "el conjunto de caracteres en una cadena".

Tenga en cuenta que un conjunto de tamaño n tiene n! n-permutaciones.

El siguiente pseudocódigo (de Wikipedia), llamado con k = 1 ... n! dará todas las permutaciones:

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;
}

Aquí está el código Python equivalente (para índices de matriz basados ​​en 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

Answer 16

Enumera las permutaciones de una cadena. Evita la duplicación cuando los caracteres se repiten:

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);
}
}

Answer 17

Esta es mi solución, que es fácil para mí entender

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 });
}

Answer 18

Me gustó el enfoque FBryant87 ya que es simple. Desafortunadamente, le gusta que muchas otras "soluciones" no ofrezcan todas las permutaciones o, por ejemplo, un número entero si contiene el mismo dígito más de una vez. Tome 656123 como un ejemplo. La línea:

var tail = chars.Except(new List<char>(){c});

Usar Except hará que se eliminen todas las ocurrencias, es decir, cuando c = 6, se eliminen dos dígitos y nos quedemos con, por ejemplo, 5123. Como ninguna de las soluciones que intenté resolvió esto, decidí intentar resolverlo por FBryant87 ''s. código como base. Esto es lo que se me ocurrió:

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;
}

Simplemente elimino la primera aparición encontrada usando .Remove y .IndexOf. Parece que funciona según lo previsto para mi uso al menos. Estoy seguro de que podría hacerse más inteligente.

Una cosa a tener en cuenta: la lista resultante puede contener duplicados, así que asegúrese de hacer que el método devuelva, por ejemplo, un HashSet en su lugar o eliminar los duplicados después de la devolución utilizando el método que desee.

Answer 19

Si el rendimiento y la memoria son un problema, sugiero esta implementación muy eficiente. Según el algoritmo de Heap en Wikipedia , debería ser el más rápido. Espero que se ajuste a tu necesidad :-)!

¡Así como la comparación de esto con una implementación de Linq para 10! (código incluido):

• Esto: 36288000 elementos en 235 milisegundos

• Linq: 36288000 artículos en 50051 milisegundos

  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");
  }
  }
  }

Answer 20

Son solo dos líneas de código si LINQ puede usar. Por favor mira mi respuesta here .

EDITAR

Aquí está mi función genérica que puede devolver todas las permutaciones (no combinaciones) de una lista de 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 }));
}

Ejemplo:

IEnumerable<IEnumerable<int>> result =
GetPermutations(Enumerable.Range(1, 3), 3);

Salida - una lista de listas enteras:

{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

Como esta función usa LINQ entonces requiere .net 3.5 o superior.

Answer 21

Versión ligeramente modificada en C # que produce las permutaciones necesarias en una matriz de CUALQUIER tipo.

 // 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;
}
}

Answer 22

La recursividad no es necesaria, here hay buena información sobre esta solución.

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();

Me han utilizado este algoritmo durante años, tiene O (N) el tiempo y la complejidad del espacio para calcular cada permutación .

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;
}
}

Answer 23

 /// <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);
}
}

Answer 24

 //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);

Answer 25

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);
}
}

Answer 26

class Program
{
static void Main(string[] args)
{
Permutation("abc");
}
static void Permutation(string rest, string prefix = "")
{
// End of recursion
if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);
// Each letter has a chance to be permutated
for (int i = 0; i < rest.Length; i++)
{
// Remove the first letter of string, append this letter to prefix
// Pass the remaining string and appended prefix to the next recursion
Permutation(rest.Remove(i, 1), prefix + rest[i]);
}
}
}

Answer 27

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]);
}
}

Puede escribir su función de intercambio para intercambiar caracteres.
Esto se llamará permute (cadena, 0);