Permutations, Combinations, and Multiples sets generator

• Download code and demo - 145.8 KB

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

// Parent class that sets inherited from.
public abstract class Set {} 
// Set where element can appear one or more such as (1,0,0) 
public class MultiplesSet:Set{ }
// Set of ordered items that mean (1,2)!=(2,1) , and number appear once in item 
public class PermutationSet : Set{ } 
// unordered array of items this mean {1,2}={2,1}, and number appear once in item 
public class CombinationSet : Set{ } 
// some helper method called by pervious classes
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).

/// <summary>
/// Parent class that sets inhireted from
/// </summary>
public abstract class Set
{
    /// <summary>
    /// last index in items == count of items
    /// </summary>
   public abstract double MaxIndex { get; }
    /// <summary>
    /// Convert integer value to series according to population.
   /// EX: MultiplesSet(4,2,3) index(0)=(0,0,0) index(1)=(0,,0,1)
   /// EX2: PermutationSet(4,2) index(0)=(0,1) index(1)=(0,2)
    /// </summary>
    /// <param name="index">integer value of index</param>
    /// <returns>Items in index as array like (0,1,2,3)</returns>
   public abstract int[] IndexToItem(double index);
    /// <summary>
    /// Given item according to population and get index of it
   /// EX: CombinationSet(5,3) item(2,3,5)=index(8)
    /// </summary>
    /// <param name="item">item as array</param>
    /// <returns>index of given item</returns>
   public abstract double ItemToIndex(int[] item);
    /// <summary>
    /// Get items in population that start with values (x1,x2x,...,xN)
    /// </summary>
    /// <param name="values">starta</param>
   /// <returns>IEnumerable of items that start with values</returns>
   public abstract IEnumerable<int[]> StartWith(params int[] values);
    /// <summary>
    /// Get items that end with values
    /// </summary>
    /// <param name="values"></param>
    /// <returns></returns>
   public abstract IEnumerable<int[]> EndWith(params int[] values);
    /// <summary>
    /// Is this item is valid in current population 
    /// EX: item(2,3,2) not valid as premutation item since it contain same item (2) twice
    /// </summary>
    /// <param name="item"></param>
    /// <returns>true if valid</returns>
   public abstract bool IsValidItem(params int[] item);

    /// <summary>
    /// all population items
    /// </summary>
   public IEnumerable<int[]> ItemsList
   {
       get
       {
           for (double i = 0; i < MaxIndex; i++)
           {
               yield return IndexToItem(i);
           }
       }
   }
   /// <summary>
   /// return all items that contain values 
   /// EX: if values(2,3) items may contain (1,2,3) or (2,5,3)
   /// if you want exactly as you write order --> use Contains method
   /// </summary>
   /// <param name="values"></param>
   /// <returns></returns>
   public IEnumerable<int[]> ContainValues(params int[] values)
   {
       foreach (int[] item in ItemsList)
       {
           if (item.ContainValues(values))
               yield return item;
       }
   }
    /// <summary>
    /// return all items that contain values
    /// </summary>
    /// <param name="values"></param>
    /// <returns></returns>
   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:

// 0,0,0,
// 0,0,1,
// 0,0,2,
// 0,0,3,
// 0,1,0,
// 0,1,1,
// 0,1,2,
// 0,1,3,
// 1,0,0,
// 1,0,1,
// 1,0,2,
// 1,0,3,
// 1,1,0,
// 1,1,1,
// 1,1,2,
// 1,1,3,
// 2,0,0,
// 2,0,1,
// 2,0,2,
// 2,0,3,
// 2,1,0,
// 2,1,1,
// 2,1,2,
// 2,1,3,

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;
        //if n=8 for example then select 8 of 8 where order is important 
        p = new PermutationSet(board_size, board_size);
    }
    /// <summary>
    /// dtermine if given array is a solution for N_Queen problem
    /// </summary>
    /// <param name="solution"></param>
    /// <returns></returns>
    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_diagonal for current item appear befor 
            //then this is not solution 
            if (right_diagonals.Contains(right_di))
                break;
            else right_diagonals.Add(right_di);
            
            //if left_diagonal for current item appear befor 
            //then this is not solution
            if (left_diagonals.Contains(left_di))
                break;
            else left_diagonals.Add(left_di);
        }
        //if all diagonals ok no one appear twice
        // then i=board size and ,and given array is valid solution 
        return i==BoardSize;
    }
    /// <summary>
    /// return array of solutions where solution is array of ints
    /// EX:solution for 8*8 board may be(0,6,3,5,7,1,4,2)
    /// this mean solution is {(0,0),(2,6),(3,3),(4,5),(5,7),(5,1),(6,4),(7,2)}
    /// </summary>
    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 [checked ok]
    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);
//get ItemsList cheked [ok]
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);
    //Parallel process on items 
}

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.