Move the list up
I am trying to get all the predefined permutations in a list in ascending order only.
For example, take the set: "ABCDE"
I'd like the returning result to be:
ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE
In other words, "B" can never appear before "A" (ascending), but I would like every variation to be within these requirements.
I would rather not use LINQ and I am trying to find the fastest way to implement this (speed is a factor in this application).
So far I have a list of character lists:
List<List<char>> Combinations;
where the inner "List" will be a combination of "ABC" (each letter is a char) and the outer list will be a list of all combinations.
The length of each result set (3 in the above example) needs to be dynamic, so I think I'll need some kind of recursion ... I just can't figure out how to implement it.
Any help would be greatly appreciated!
EDIT
So far, here's what I have (I feel like I'm getting closer ... I just can't get him to actually make the final list (union doesn't work - am I using it wrong)?
private List<List<char>> AscendingPermute(List<char> InMovements, int Combinations)
{
List<List<char>> Ret = new List<List<char>>();
for(int i = 0; i <= InMovements.Count - Combinations; i++)
{
if(Combinations <= 1){
Ret.Add(new List<char>() {InMovements[i] });
return Ret;
}
else
{
Ret.Union(AscendingPermute(InMovements.GetRange(1, InMovements.Count - 1), Combinations - 1));
}
}
return Ret;
}
Am I on the right track? What am I missing?
Thank!
source to share
I think this is what you are looking for, although I'm not sure about the speed:
public static IEnumerable<string> GetPermutations(string letters, int max = 3, int curr = 0)
{
if (curr < max - 1)
{
for (int a = 0; a < letters.Length; a++)
{
string firstHalf = letters.Substring(a,1);
string subset = letters.Substring(a+1);
foreach (string secondHalf in GetPermutations(subset, max, curr + 1))
{
//Console.Write("1st: {0}, 2nd: {1}; set: {2}", firstHalf, secondHalf, subset);
yield return firstHalf + secondHalf;
}
}
}
else
yield return String.Empty;
}
Call example:
foreach (var result in GetPermutations('ABCDE', 3)){
Console.WriteLine(result);
}
Results in:
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
Press any key to continue...
source to share
So you want all possible k-elements to be from a set of n elements, and you want each list of k-elements in ascending order?
Look here: Algorithm to return all combinations of k elements from n
source to share
No need for recursion.
List<string> sortedResult = Perm("ABCDE",3);
static int BitCount(int n)
{
int test = n,count = 0;
while (test != 0)
{
if ((test & 1) == 1) count++;
test >>= 1;
}
return count;
}
static List<string> Perm(string input,int M)
{
var chars = input.ToCharArray();
int N = chars.Length;
List<List<char>> result = new List<List<char>>();
for (int i = 0; i < Math.Pow(2, N); i++)
{
if (BitCount(i) == M)
{
List<char> line = new List<char>();
for (int j = 0; j < N; j++)
{
if (((i >> j) & 1) == 1)
{
line.Add(chars[j]);
}
}
result.Add(line);
}
}
return result.Select(l => String.Join("", l)).OrderBy(s => s).ToList();
}
source to share
You are looking for a recursive function that will compute: the first letter in a given alphabet (sorted in ascending order), combined with upward permutations with one smaller letter of the remainder of the alphabet, plus upward permutations of the remainder with the same number of letters.
To clarify, for your example it is
asc_perm("ABCDE",3):="A"+asc_perm("BCDE",2) | asc_perm("BCDE",3)
To program it iteratively, you can have indices n
in your constrained alphabet n>m => idx_{n} > idx_{m}
and 0 < n,m <= count(alphabet)
and list all possible indices. This is a kind of counter with some additional conditions. To calculate the usage of these indices, you start with 1, 2, 3, 4, ...n
. Start by increasing the last counter until it reaches the length of the alphabet. When this happens, find the previous index, increase it by 1, and set each index following it to a value 1+idx_prev
until the indexes are larger than your score. If so, you repeat the process at the previous index until you end up with valid positions.
A simple example of your example:
- Initial condition:
{1,2,3}
- Run last index for all admissible positions:
{1,2,4}
,{1,2,5}
- Add the previous index (2) to the next and reset the rest:
{1,3,4}
- Run the last index for all valid positions:
{1,3,5}
- Add the previous index (2) to the next and reset the rest:
{1,4,5}
- Run the last index for all valid positions: no possible moves
- Increase the previous index (2) to the next one and reset the rest: no possible moves
- Add the previous index (1) to the next and reset the rest:
{2,3,4}
- Run the last index for all valid positions:
{2,3,5}
- Add the previous index (2) to the next and reset the rest:
{2,4,5}
- Run the last index for all valid positions: no possible moves
- Increase the previous index (2) to the next one and reset the rest: no possible moves
- Add the previous index (1) to the next and reset the rest:
{3,4,5}
- Run the last index for all valid positions: no possible moves
- Increase the previous index (2) to the next one and reset the rest: no possible moves
- Add the previous index (1) to the next and reset the rest: no possible moves
- Abort
source to share
Here's a recursive method that does what you want:
static IEnumerable<List<byte>> AscPerm(List<byte> inBytes, int combinations)
{
if (combinations == 1)
{
foreach (var b in inBytes)
{
yield return new List<byte> { b };
}
}
else
{
for (int i = 0; i <= inBytes.Count - combinations; i++)
{
// Recurse down, passing last items of inBytes.
var subPerms = AscPerm(inBytes.Skip(i +1).ToList(), combinations - 1);
foreach (var subPerm in subPerms)
{
List<byte> retBytes = new List<byte>{ inBytes[i] };
yield return retBytes.Concat(subPerm).ToList();
}
}
}
}
static void Main(string[] args)
{
var retList = AscPerm(new List<byte> { 1, 2, 3, 4, 5, 6, 7 }, 3);
foreach (var ret in retList)
{
foreach (var r in ret)
{
Console.Write(r);
}
Console.WriteLine();
}
Console.ReadLine();
}
source to share