Items Combinations Generation Library

Posted by Ahmed Tarek Hasan on 2/27/2013 08:44:00 PM with No comments
[Update] This library is now replaced with a new one. The new one is more advanced and enhanced. You can check it on Possibilities Cube Library - A Library Smart Enough To Calculate All Possibilities With Logical Conditions


Sometimes you have a set of items (could be numbers, names, custom entities, .....) and you need to get all possible combinations each consists of a given number of items from the bigger set.

To understand what I am saying, imagine that you need to write a program by which a user can define some birthday gifts. Each gift has an id, name, description, price, ...... Your program is expected to provide all possible combinations of gifts that a father can get to his son given that the number of gift items doesn't exceed 5 and the price doesn't exceed LE 150.

To solve the problem above, which is a mathematical problem in the first place, you can use some of the mathematical algorithms. But, only for the sake of demonstration, I will assume that we will use a brute force approach to solve the problem.

So, to do the job, at some point in your code, you will need to generate all the possibilities and combinations of gift items that the father can buy for his son. Sure not all these combinations are valid and you will need to filter them according to your business but at least it is a starting point.

So, to get all possible combinations, you can use the same logic used in the binary tables. For example, in binary, any bit can be 0 or 1 and nothing else. So, if we need to have all possible sets consisting of 2 bits, we will get
0 , 0
0 , 1
1 , 0
1 , 1

These are all possible combinations you can get in this case. But, in case of sets consisting of 3 bits instead of 2, we will get
0 , 0 , 0
0 , 0 , 1
0 , 1 , 0
0 , 1 , 1
1 , 0 , 0
1 , 0 , 1
1 , 1 , 0
1 , 1 , 1

and so on........

So, this leads us to the "Items Combinations Generation Library" that I am presenting. This library provides a class with some methods which you can use to get all possible combinations of any set of items. It returns an array of indexes of items you have. So, when you get [(0 , 0), (0 , 1), (1 , 0), (1 , 1)] these numbers refer to the indexes of the items in your collection of items.

Ok, this is the time for the code.


The Library Code

Possibilities.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DevelopmentSimplyPut.CommonUtilities
{
    public class Possibilities
    {
        #region Properties
        int numberOfItems;
        public int NumberOfItems
        {
            get { return numberOfItems; }
            set 
            {
                if (value > 0)
                {
                    numberOfItems = value;
                }
                else
                {
                    throw new Exception("NumberOfItems must be +ve and greater than 0.");
                }
            }
        }
        int numberOfInstancesPerPossibility;
        public int NumberOfInstancesPerPossibility
        {
            get { return numberOfInstancesPerPossibility; }
            set
            {
                if (value > 0)
                {
                    numberOfInstancesPerPossibility = value;
                }
                else
                {
                    throw new Exception("NumberOfInstancesPerPossibility must be +ve and greater than 0.");
                }
            }
        }
        int maxRowIndex;
        int maxColumnIndex;
        #endregion Properties

        #region Constructors
        public Possibilities(int _numberOfItems, int _numberOfInstancesPerPossibility)
        {
            NumberOfItems = _numberOfItems;
            NumberOfInstancesPerPossibility = _numberOfInstancesPerPossibility;
            maxRowIndex = intPow(NumberOfItems, NumberOfInstancesPerPossibility) - 1;
            maxColumnIndex = NumberOfInstancesPerPossibility - 1;
        }
        #endregion Constructors

        #region Methods
        public int[,] GetPossibilities()
        {
            int[,] result = new int[maxRowIndex + 1, maxColumnIndex + 1];

            for (int i = 0; i <= maxRowIndex; i++)
            {
                int[] rowResults = GetPossiblityByIndex(i);
                for (int k = 0; k < rowResults.Length; k++)
                {
                    result[i, k] = rowResults[k];
                }
            }
            
            return result;
        }
        public int[] GetPossiblityByIndex(int rowIndex)
        {
            int[] result = null;

            if (rowIndex >= 0)
            {
                if (rowIndex <= maxRowIndex)
                {
                    result = new int[maxColumnIndex + 1];

                    for (int i = 0; i <= maxColumnIndex; i++)
                    {
                        result[i] = GetPossiblityByIndex(rowIndex, i);
                    }
                }
                else
                {
                    throw new Exception(string.Format("rowIndex can not be greater than {0}", maxRowIndex));
                }
            }
            else
            {
                throw new Exception("rowIndex must be +ve or equal to 0.");
            }

            return result;
        }
        public int GetPossiblityByIndex(int rowIndex, int columnIndex)
        {
            int result = 0;

            if (rowIndex >= 0 && columnIndex >= 0)
            {
                if (rowIndex > maxRowIndex)
                {
                    throw new Exception(string.Format("rowIndex can not be greater than {0}", maxRowIndex));
                }
                else if (columnIndex > maxColumnIndex)
                {
                    throw new Exception(string.Format("columnIndex can not be greater than {0}", maxColumnIndex));
                }
                else
                {
                    int numberOfHops = intPow(NumberOfItems, columnIndex);
                    result = GetPossiblityByIndex(NumberOfItems, numberOfHops, rowIndex);
                }
            }
            else
            {
                throw new Exception("rowIndex and columnIndex must be +ve or equal to 0.");
            }

            return result;
        }
        private int GetPossiblityByIndex(int numberOfItems, int numberOfHops, int rowIndex)
        {
            int result = 0;
            int maxItemIndex = numberOfItems - 1;
            result = rowIndex / numberOfHops;
            result = result % numberOfItems;
            return result;
        }
        private int intPow(int a, int b)
        {
            int result = 0;

            if (0 == b)
            {
                result = 1;
            }
            else if (1 == b)
            {
                result = a;
            }
            else
            {
                result = a;
                for (int i = 0; i < b - 1; i++)
                {
                    result *= a;
                }
            }
            
            return result;
        }
        #endregion Methods
    }
}


Testing Windows Forms Application

MainForm.Designer.cs
namespace TestApp
{
    partial class MainForm
    {
        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.btnRun = new System.Windows.Forms.Button();
            this.label1 = new System.Windows.Forms.Label();
            this.label2 = new System.Windows.Forms.Label();
            this.txtNumOfItems = new System.Windows.Forms.TextBox();
            this.txtNumOfInstances = new System.Windows.Forms.TextBox();
            this.rtxtOutput = new System.Windows.Forms.RichTextBox();
            this.SuspendLayout();
            // 
            // btnRun
            // 
            this.btnRun.Location = new System.Drawing.Point(264, 6);
            this.btnRun.Name = "btnRun";
            this.btnRun.Size = new System.Drawing.Size(47, 54);
            this.btnRun.TabIndex = 0;
            this.btnRun.Text = "Run";
            this.btnRun.UseVisualStyleBackColor = true;
            this.btnRun.Click += new System.EventHandler(this.btnRun_Click);
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(4, 12);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(85, 13);
            this.label1.TabIndex = 1;
            this.label1.Text = "Number of items";
            // 
            // label2
            // 
            this.label2.AutoSize = true;
            this.label2.Location = new System.Drawing.Point(4, 40);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(105, 13);
            this.label2.TabIndex = 2;
            this.label2.Text = "Number of instances";
            // 
            // txtNumOfItems
            // 
            this.txtNumOfItems.Location = new System.Drawing.Point(116, 9);
            this.txtNumOfItems.Name = "txtNumOfItems";
            this.txtNumOfItems.Size = new System.Drawing.Size(137, 20);
            this.txtNumOfItems.TabIndex = 3;
            // 
            // txtNumOfInstances
            // 
            this.txtNumOfInstances.Location = new System.Drawing.Point(115, 40);
            this.txtNumOfInstances.Name = "txtNumOfInstances";
            this.txtNumOfInstances.Size = new System.Drawing.Size(137, 20);
            this.txtNumOfInstances.TabIndex = 4;
            // 
            // rtxtOutput
            // 
            this.rtxtOutput.Location = new System.Drawing.Point(8, 66);
            this.rtxtOutput.Name = "rtxtOutput";
            this.rtxtOutput.Size = new System.Drawing.Size(299, 217);
            this.rtxtOutput.TabIndex = 5;
            this.rtxtOutput.Text = "";
            // 
            // MainForm
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(315, 291);
            this.Controls.Add(this.rtxtOutput);
            this.Controls.Add(this.txtNumOfInstances);
            this.Controls.Add(this.txtNumOfItems);
            this.Controls.Add(this.label2);
            this.Controls.Add(this.label1);
            this.Controls.Add(this.btnRun);
            this.Name = "MainForm";
            this.Text = "Test Application";
            this.ResumeLayout(false);
            this.PerformLayout();

        }

        #endregion

        private System.Windows.Forms.Button btnRun;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.Label label2;
        private System.Windows.Forms.TextBox txtNumOfItems;
        private System.Windows.Forms.TextBox txtNumOfInstances;
        private System.Windows.Forms.RichTextBox rtxtOutput;
    }
}

MainForm.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
using DevelopmentSimplyPut.CommonUtilities;

namespace TestApp
{
    public partial class MainForm : Form
    {
        public MainForm()
        {
            InitializeComponent();
        }

        private void btnRun_Click(object sender, EventArgs e)
        {
            rtxtOutput.Text = string.Empty;

            Possibilities container = new Possibilities(int.Parse(txtNumOfItems.Text), int.Parse(txtNumOfInstances.Text));
            int[,] allPossibilities = container.GetPossibilities();

            for (int i = 0; i < allPossibilities.GetLength(0); i++)
            {
                for (int k = 0; k < allPossibilities.GetLength(1); k++)
                {
                    rtxtOutput.Text += allPossibilities[i, k].ToString() + " , ";
                }

                rtxtOutput.Text += Environment.NewLine;
            }

            MessageBox.Show("Done");
        }
    }
}

Running this program you will get the results in the screenshots below

Items Combinations Generation Library

Items Combinations Generation Library

Items Combinations Generation Library


Finally, you can download the source code from here



Categories: , ,