I have 5 strings, such as: "one", "two", "three", "four", and "five". I need to get all permutations of these strings. I've explored all internet resources, but all solutions are so bulky and it's hard for me to understand it and integrate it to my program.
So, maybe you know any easy solution how to get permutations.
-
1Permutations of the strings to mean order in which they are stored or do you mean the order of the individual characters in each string?AndyPerfect– AndyPerfect2011-02-26 17:50:27 +00:00Commented Feb 26, 2011 at 17:50
-
It means order in which they're stored. Words order.Frankie Drake– Frankie Drake2011-02-26 17:52:43 +00:00Commented Feb 26, 2011 at 17:52
-
Do you want "oneoneoneoneone", "oneoneoneonetwo" all the way to "fivefivefivefivefive"?Brian Rasmussen– Brian Rasmussen2011-02-26 17:58:57 +00:00Commented Feb 26, 2011 at 17:58
-
No-no. For example: 123. It would: 123, 132, 213, 231, 312, 321.Frankie Drake– Frankie Drake2011-02-26 18:03:08 +00:00Commented Feb 26, 2011 at 18:03
Add a comment
|
6 Answers
Permutations are very easy to do.
/// <summary>
/// Returns all permutations of the input <see cref="IEnumerable{T}"/>.
/// </summary>
/// <param name="source">The list of items to permute.</param>
/// <returns>A collection containing all permutations of the input <see cref="IEnumerable<T>"/>.</returns>
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
{
if (source == null)
throw new ArgumentNullException("source");
// Ensure that the source IEnumerable is evaluated only once
return permutations(source.ToArray());
}
private static IEnumerable<IEnumerable<T>> permutations<T>(IEnumerable<T> source)
{
var c = source.Count();
if (c == 1)
yield return source;
else
for (int i = 0; i < c; i++)
foreach (var p in permutations(source.Take(i).Concat(source.Skip(i + 1))))
yield return source.Skip(i).Take(1).Concat(p);
}
Comments
Here's a class that works in .Net 2.0. First, sort your array. Then use it by looping over while(Permute.Next(array)). When there are no more permutations, Permute.Next returns false.
using System;
using System.Collections.Generic;
using System.Text;
public class Permute
{
public static bool Next(IList<IComparable> list)
{
int k = FindSmallestK(list);
if (k < 0) return false;
int l = FindLargestL(list, k);
Swap(list, k, l);
Reverse(list, k + 1);
return true;
}
private static void Reverse(IList<IComparable> list, int p)
{
for (int i = p, j = list.Count - 1; i < j; i++, j--)
{
Swap(list, i, j);
}
}
private static void Swap(IList<IComparable> list, int k, int l)
{
IComparable temp = list[k];
list[k] = list[l];
list[l] = temp;
}
private static int FindLargestL(IList<IComparable> list, int k)
{
for (int i = list.Count - 1; i > k; i--)
{
if (list[k].CompareTo(list[i]) < 0) return i;
}
return -1;
}
private static int FindSmallestK(IList<IComparable> list)
{
for (int i = 0; i < list.Count - 1; i++)
{
if (list[i].CompareTo(list[i + 1]) < 0) return i;
}
return -1;
}
}
Comments
This article shows the complete code for getting all permutations of letters. Substitute letters with words and you have your solution:
4 Comments
Frankie Drake
Thanx, I've tried to modify it, but I can't yet. No matter what this example is very very good.
Frankie Drake
So have you any ideas, how to modify it, cause this code use CharArray. How to make it using string[]?
Frankie Drake
Oh, I'm sorry, it was my stupid mistake! I have another problem at all! I need COMBINATIONS!!
Jakub Konecki
You might want to edit your question as it has Permutations written all over it...
This is a pretty nice combinatorics library - http://www.codeproject.com/KB/recipes/Combinatorics.aspx
Comments
The permutation article on wikipedia has a good summary of some example algorithms
http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
answered Feb 26, 2011 at 17:50
Brandon Frohbieter
18.2k4 gold badges42 silver badges62 bronze badges
Comments
using System.Collections.Generic;
using System.Linq;
namespace caComb
{
class Program
{
private static List<List<string>> allCombinations = new List<List<string>>();
static void Main(string[] args)
{
string[] words = new string[] { "one", "two", "three", "four", "five" };
List<string> temp = new List<string>();
GetCombinations(words, temp);
// Here you can read all combinations from
// allCombinations. Do whatever you want.
}
private static void GetCombinations(string[] words, List<string> temp)
{
if (temp.Count == words.Length)
{
List<string> clone = temp.ToList();
if (clone.Distinct().Count() == clone.Count)
{
allCombinations.Add(clone);
}
return;
}
for (int i = 0; i < words.Length; i++)
{
temp.Add(words[i]);
GetCombinations(words, temp);
temp.RemoveAt(temp.Count - 1);
}
}
}
}
