Introduction
The solution too many software problems involves being able to select number of points in a sample space. Selecting points can be hard, tedious, or both.
Before we find our population we must know count of items in it, there is ways to make the counting task easier. Such as Items multiples', permutations', and combinations.
The main idea in this code is how to maintain population list without list, to save memory space and enter this virtual list to get items from it (Hint: set items not allowed
since population is not modified), for example if we have 15 items and we want to select 9 items of it without recursion the population size will nPr(15,9)=1816214400,
this population is very large, maintain a list here is not option.
How this run, if we able to convert index to correspond item in population virtual list , and item to index then the problem is solved. if you don’t understand what I mean read next.
Project classes
public abstract class Set {}
public class MultiplesSet:Set{ }
public class PermutationSet : Set{ }
public class CombinationSet : Set{ }
public static class Methods{ }
Parent Class (Set)
In this code we implement the abstract class (Set
) for three basic population sets (multiples, permutations, and combinations).
public abstract class Set
{
public abstract double MaxIndex { get; }
public abstract int[] IndexToItem(double index);
public abstract double ItemToIndex(int[] item);
public abstract IEnumerable<int[]> StartWith(params int[] values);
public abstract IEnumerable<int[]> EndWith(params int[] values);
public abstract bool IsValidItem(params int[] item);
public IEnumerable<int[]> ItemsList
{
get
{
for (double i = 0; i < MaxIndex; i++)
{
yield return IndexToItem(i);
}
}
}
public IEnumerable<int[]> ContainValues(params int[] values)
{
foreach (int[] item in ItemsList)
{
if (item.ContainValues(values))
yield return item;
}
}
public virtual IEnumerable<int[]> Contains(params int[] values)
{
if (IsValidItem(values))
{
foreach (int[] item in ItemsList)
{
if (item.ContainSubArray(values))
yield return item;
}
}
}
}
MultiplesSet class
If you have three groups where items count in each group is (3,2,4) respectively and want to select 3 items (take one of each group)then use MultiplesSet
class as the following:
MultiplesSet c = new MultiplesSet(3,2,4);
foreach (int[] item in c.ItemsList)
{
Console.WriteLine(ElementToString(item));
}
Output of this will be:
PermutationSet class
I will solve N_Queen problem using PermutationSet
class, first look to this image
- Red = first item = x
- Blue = second item = y
- Black = left diagonal = first + second = x + y
- Green = right diagonal = ((board size - 1) – x) + y = (7- x) + y
EX: given (2,5) board square axis find left diagonal and right diagonal? Left diagonal = 2+5 = 7,Right diagonal = (7-2) + 5 = 10.
The following code solve N_queen problem using PermutationSet
class (same idea in this
link
but replace genetic algorithm by PermutationSet
generator class)
class NQueen_Example
{
int BoardSize;
PermutationSet p;
public NQueen_Example(int board_size)
{
BoardSize = board_size;
p = new PermutationSet(board_size, board_size);
}
public bool IS_Correct(ref int[] solution)
{
List<int> right_diagonals = new List<int>();
List<int> left_diagonals = new List<int>();
int i;
for (i = 0; i < solution.Length; i++)
{
int left_di = i + solution[i];
int right_di = (BoardSize - 1 - i) + solution[i];
if (right_diagonals.Contains(right_di))
break;
else right_diagonals.Add(right_di);
if (left_diagonals.Contains(left_di))
break;
else left_diagonals.Add(left_di);
}
return i==BoardSize;
}
public IEnumerable<int[]> CorrectSolutions
{
get
{
for (double i = 0; i < p.MaxIndex; i++)
{
int[] solution = p.IndexToItem(i);
if (IS_Correct(ref solution))
yield return solution;
}
}
}
}
If we call instance of this class in main as this:
static void Main(string[] args)
{
NQueen_Example nq = new NQueen_Example(8);
foreach (int[] solution in nq.CorrectSolutions)
{
Console.WriteLine("{0}",
ElementToString(solution));
}
}
Output will 92 item as this:
0,4,7,5,2,6,1,3,
0,5,7,2,6,3,1,4,
0,6,3,5,7,1,4,2,
0,6,4,7,1,3,5,2,
1,3,5,7,2,0,6,4,
1,4,6,0,2,7,5,3,
1,4,6,3,0,7,5,2,
1,5,0,6,3,7,2,4,
1,5,7,2,0,3,6,4,
1,6,2,5,7,4,0,3,
1,6,4,7,0,3,5,2,
..........
..........
7,3,0,2,5,1,6,4,
CombinationSet class using
If you have 9 items of anything and want to select 5 items of it, where order of this item is not important this mean {1,2,3,4,5} equal {5,2,3,4,1}. Here code that you can use:
CombinationSet c = new CombinationSet(9, 5);
foreach (int[] item in c.ItemsList)
{
Console.WriteLine(ElementToString(item));
}
Output will nCr(9,5)
= 126 item as this:
1,2,3,4,5,
1,2,3,4,5,
1,2,3,4,6,
1,2,3,4,7,
1,2,3,4,8,
1,2,3,4,9,
1,2,3,5,6,
1,2,3,5,7,
1,2,3,5,8,
1,2,3,5,9,
1,2,3,6,7,
1,2,3,6,8,
1,2,3,6,9,
1,2,3,7,8,
…….
….
4,5,6,7,8,9
Hint: CombinationSet
class is one based index ,this mean first item index is 1 not zero , also items list first item is 1,2,3,4,5 not 0,1,2,3,4.
Points of Interest
StartWith
, EndWith
methods does not maintains a loop through ItemsList
, it is mathematics enhanced, this mean find first item index
and last item index , then return values between them. And of course IndexToItem
and ItemToIndex
methods will give you sense of using lists.
Threading programming on these set will be easy now take this as example:
CombinationSet c = new CombinationSet(9, 5)
Parallel.For(1,(Int64)c.MaxIndex, (i) =>
{
int[] item=c.IndexToItem(i);
}
You can use these classes in many applications, and you can extend it easily. If you have any suggestions send it as replay message please.
[Hint] This article may contain grammatical and spelling errors, if you silver member or high you can correct this error.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.