Possibilities Cube Library - A Library Smart Enough To Calculate All Possibilities With Logical Conditions
Posted by on 8/07/2013 09:33:00 PM with No comments
Let's imagine that as a big advertisement campaign Vodafone, Samsung & Nokia co-arranged a lottery. The winner will get two mobile phones in addition to two SIM cards with special numbers.
It is obvious that the SIM cards will be provided by Vodafone while the mobile phones manufacturer will be decided by toss, so the winner may get two phones from Samsung or Nokia or both. Also, the phones specifications will be somehow restricted as in the image below.
So, if we try to guess all the possible combinations of any of the phones, we can work it out and get the results as in the image below.
This was somehow easy as the possibilities are not that large. But what about guessing all the possible combinations of the two phones at the same time?
This time it is not that easy due to the large number of possibilities. As we can see there are 64 possibilities and this is because each phone can be one of 8 phone combinations and we have 2 phones, then 8 * 8 = 64
What if I told you that we need to re-visit the phones combinations are there is something not logical. We know that Samsung doesn't produce phones with Symbian as OS. So, we need to cancel the phone combination which includes both Samsung and Symbian.
Also, if the lottery managers said that the two mobile phones can't be identical or exactly the same which means that at least one phone specification should be differ between both phones.
All these logical restrictions should be included in our calculations to finally get all possible combinations we need.
If we try to visualize the whole thing, we can see it into the image below.
Now, how about if I tell you that there is a library which you can use to calculate such calculations and you can define your own logical restrictions to filter out all logically refused combinations, will you like to use this library?
Here come the PossibilitiesCube library.
PossibilitiesCube.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DevelopmentSimplyPut.CommonUtilities
{
public class PossibilitiesCube
{
#region Properties
public Func<Int64[], bool> AttributesCombinationValidator { set; get; }
public Func<Int64[], bool> InstancesCombinationValidator { set; get; }
public Func<Int64[], Int64[,], bool> FinalCombinationValidator { set; get; }
public Int64 InstancesCombinationsMaxRowIndex
{
get
{
return instancesCombinations.GetLength(0) - 1;
}
}
public Int64 InstancesCombinationsMaxColumnIndex
{
get
{
return instancesCombinations.GetLength(1) - 1;
}
}
public Int64 AttributesCombinationsMaxRowIndex
{
get
{
return attributesCombinations.GetLength(0) - 1;
}
}
public Int64 AttributesCombinationsMaxColumnIndex
{
get
{
return attributesCombinations.GetLength(1) - 1;
}
}
bool combinationsExist;
public bool CombinationsExist
{
get
{
return combinationsExist;
}
}
#endregion Properties
#region Fields
Int64 numberOfInstances;
Int64 instancesCombinationsMaxRowIndex;
Int64 instancesCombinationsMaxColumnIndex;
Int64 attributesCombinationsMaxRowIndex;
Int64 attributesCombinationsMaxColumnIndex;
Int64[,] attributesCombinations;
Int64[,] instancesCombinations;
Int64[] attributesPoolsSizes;
#endregion
#region Indexers
public Int64 this[Int64 instancesCombinationIndex, Int64 instanceIndex, Int64 attributeIndex]
{
get
{
return GetAttributesCombination(instancesCombinations[instancesCombinationIndex, instanceIndex])[attributeIndex];
}
}
public Int64[] this[Int64 instancesCombinationIndex, Int64 instanceIndex]
{
get
{
return GetAttributesCombination(instancesCombinations[instancesCombinationIndex, instanceIndex]);
}
}
public Int64[] this[Int64 instancesCombinationIndex]
{
get
{
Int64[] result = new Int64[instancesCombinations.GetLength(1)];
for (Int64 i = 0; i <= instancesCombinations.GetLength(1); i++)
{
result[i] = instancesCombinations[instancesCombinationIndex, i];
}
return result;
}
}
#endregion
#region Constructors
public PossibilitiesCube(Int64 _numberOfInstances, params Int64[] _attributesPoolsSizes)
{
if (_numberOfInstances <= 0)
{
throw new Exception("NumberOfInstancesPerPossibility must be +ve and greater than 0.");
}
numberOfInstances = _numberOfInstances;
attributesPoolsSizes = _attributesPoolsSizes;
attributesCombinationsMaxRowIndex = 1;
foreach (Int64 size in _attributesPoolsSizes)
{
attributesCombinationsMaxRowIndex *= size;
}
attributesCombinationsMaxRowIndex--;
attributesCombinationsMaxColumnIndex = _attributesPoolsSizes.Length - 1;
}
#endregion Constructors
#region Methods
public Int64[] GetAttributesCombination(Int64 index)
{
Int64[] result = new Int64[attributesCombinations.GetLength(1)];
for (Int64 i = 0; i < attributesCombinations.GetLength(1); i++)
{
result[i] = attributesCombinations[index, i];
}
return result;
}
private void GetPossibilities()
{
Int64[,] result = new Int64[instancesCombinationsMaxRowIndex + 1, instancesCombinationsMaxColumnIndex + 1];
Int64 numberOfFilteredOutPossibilities = 0;
for (Int64 i = 0; i <= instancesCombinationsMaxRowIndex; i++)
{
Int64[] rowResults = GetPossiblityByIndex(i, instancesCombinationsMaxRowIndex, instancesCombinationsMaxColumnIndex, InstancesCombinationValidator, OperationMode.Instances);
if (rowResults[0] == -1)
{
numberOfFilteredOutPossibilities++;
}
else if(null != FinalCombinationValidator)
{
if(!FinalCombinationValidator(rowResults, attributesCombinations))
{
rowResults[0] = -1;
numberOfFilteredOutPossibilities++;
}
}
for (Int64 k = 0; k < rowResults.Length; k++)
{
result[i, k] = rowResults[k];
}
}
Int64[,] finalResult;
Int64 actualNumberOfPossibilities = instancesCombinationsMaxRowIndex + 1 - numberOfFilteredOutPossibilities;
if (actualNumberOfPossibilities > 0)
{
finalResult = new Int64[actualNumberOfPossibilities, instancesCombinationsMaxColumnIndex + 1];
Int64 actualRowIndex = 0;
for (Int64 i = 0; i < instancesCombinationsMaxRowIndex + 1; i++)
{
if (result[i, 0] != -1)
{
for (Int64 k = 0; k < instancesCombinationsMaxColumnIndex + 1; k++)
{
finalResult[actualRowIndex, k] = result[i, k];
}
actualRowIndex++;
}
}
combinationsExist = true;
}
else
{
finalResult = new Int64[1, instancesCombinationsMaxColumnIndex + 1];
for (Int64 k = 0; k < instancesCombinationsMaxColumnIndex + 1; k++)
{
finalResult[0, k] = -1;
}
combinationsExist = false;
}
instancesCombinations = finalResult;
}
public void BuildPossibilitiesMatrix()
{
Int64[,] result = new Int64[attributesCombinationsMaxRowIndex + 1, attributesCombinationsMaxColumnIndex + 1];
Int64 numberOfFilteredOutPossibilities = 0;
for (Int64 i = 0; i <= attributesCombinationsMaxRowIndex; i++)
{
Int64[] rowResults = GetPossiblityByIndex(i, attributesCombinationsMaxRowIndex, attributesCombinationsMaxColumnIndex, AttributesCombinationValidator, OperationMode.Attributes);
if (rowResults[0] == -1)
{
numberOfFilteredOutPossibilities++;
}
for (Int64 k = 0; k < rowResults.Length; k++)
{
result[i, k] = rowResults[k];
}
}
Int64[,] finalResult;
Int64 actualNumberOfPossibilities = attributesCombinationsMaxRowIndex + 1 - numberOfFilteredOutPossibilities;
if (actualNumberOfPossibilities > 0)
{
finalResult = new Int64[actualNumberOfPossibilities, attributesCombinationsMaxColumnIndex + 1];
Int64 actualRowIndex = 0;
for (Int64 i = 0; i < attributesCombinationsMaxRowIndex + 1; i++)
{
if (result[i, 0] != -1)
{
for (Int64 k = 0; k < attributesCombinationsMaxColumnIndex + 1; k++)
{
finalResult[actualRowIndex, k] = result[i, k];
}
actualRowIndex++;
}
}
instancesCombinationsMaxRowIndex = intPow(actualNumberOfPossibilities, numberOfInstances) - 1;
instancesCombinationsMaxColumnIndex = numberOfInstances - 1;
}
else
{
finalResult = new Int64[1, attributesCombinationsMaxColumnIndex + 1];
for (Int64 k = 0; k < attributesCombinationsMaxColumnIndex + 1; k++)
{
finalResult[0, k] = -1;
}
instancesCombinationsMaxRowIndex = 0;
instancesCombinationsMaxColumnIndex = 0;
}
attributesCombinations = finalResult;
GetPossibilities();
}
private Int64[] GetPossiblityByIndex(Int64 rowIndex, Int64 maxRowIndex, Int64 maxColumnIndex, Func<Int64[], bool> validator, OperationMode mode)
{
Int64[] result = null;
if (rowIndex >= 0)
{
if (rowIndex <= maxRowIndex)
{
result = new Int64[maxColumnIndex + 1];
for (Int64 i = 0; i <= maxColumnIndex; i++)
{
result[i] = GetPossiblityByIndex(rowIndex, i, maxRowIndex, maxColumnIndex, mode);
}
if (null != validator)
{
if (!validator(result))
{
for (Int64 i = 0; i <= maxColumnIndex; i++)
{
result[i] = -1;
}
}
}
}
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;
}
private Int64 GetPossiblityByIndex(Int64 rowIndex, Int64 columnIndex, Int64 maxRowIndex, Int64 maxColumnIndex, OperationMode mode)
{
Int64 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
{
Int64 numberOfHops = 1;
Int64 numOfItems = 1;
switch (mode)
{
case OperationMode.Attributes:
numOfItems = attributesPoolsSizes[columnIndex];
if (columnIndex == 0)
{
numberOfHops = 1;
}
else
{
numberOfHops = 1;
for (Int64 i = 0; i < columnIndex; i++)
{
numberOfHops *= attributesPoolsSizes[i];
}
}
break;
case OperationMode.Instances:
numOfItems = attributesCombinations.GetLength(0);
numberOfHops = intPow(numOfItems, columnIndex);
break;
}
result = GetPossiblityByIndex(numOfItems, numberOfHops, rowIndex);
}
}
else
{
throw new Exception("rowIndex and columnIndex must be +ve or equal to 0.");
}
return result;
}
private Int64 GetPossiblityByIndex(Int64 numberOfItems, Int64 numberOfHops, Int64 rowIndex)
{
Int64 result = 0;
result = rowIndex / numberOfHops;
result = result % numberOfItems;
return result;
}
private Int64 intPow(Int64 a, Int64 b)
{
Int64 result = 0;
if (0 == b)
{
result = 1;
}
else if (1 == b)
{
result = a;
}
else
{
result = a;
for (Int64 i = 0; i < b - 1; i++)
{
result *= a;
}
}
return result;
}
#endregion Methods
}
public enum OperationMode
{
Attributes = 0,
Instances = 1
}
}
How to use the library?
The library is somehow simple in usage but always keep in mind the complexity of the task it is about to carry out. To see how simple it is you can check the test application below.
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.rtxtOutput = new System.Windows.Forms.RichTextBox();
this.SuspendLayout();
//
// btnRun
//
this.btnRun.Location = new System.Drawing.Point(86, 312);
this.btnRun.Name = "btnRun";
this.btnRun.Size = new System.Drawing.Size(149, 33);
this.btnRun.TabIndex = 0;
this.btnRun.Text = "Get All Prizes Combinations";
this.btnRun.UseVisualStyleBackColor = true;
this.btnRun.Click += new System.EventHandler(this.btnRun_Click);
//
// rtxtOutput
//
this.rtxtOutput.Location = new System.Drawing.Point(12, 2);
this.rtxtOutput.Name = "rtxtOutput";
this.rtxtOutput.Size = new System.Drawing.Size(299, 304);
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(321, 347);
this.Controls.Add(this.rtxtOutput);
this.Controls.Add(this.btnRun);
this.Name = "MainForm";
this.Text = "Test Application";
this.ResumeLayout(false);
}
#endregion
private System.Windows.Forms.Button btnRun;
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;
using System.Globalization;
namespace TestApp
{
public partial class MainForm : Form
{
public MainForm()
{
InitializeComponent();
}
private void btnRun_Click(object sender, EventArgs e)
{
rtxtOutput.Text = string.Empty;
string[] colors = new string[2] { "White", "Black" };
string[] brands = new string[2] { "Nokia", "Samsung" };
string[] os = new string[2] { "Symbian", "Android" };
Int64[] attributesSizes = new Int64[3];
attributesSizes[0] = colors.Length;
attributesSizes[1] = brands.Length;
attributesSizes[2] = os.Length;
PossibilitiesCube container = new PossibilitiesCube(2, attributesSizes);
container.AttributesCombinationValidator = new Func<Int64[], bool>
(
delegate(Int64[] attributesCombination)
{
bool result = true;
//filter out if the brand is "Samsung" and the os is "Symbian"
if (attributesCombination[1] == 1 && attributesCombination[2] == 0)
{
result = false;
}
return result;
}
);
container.InstancesCombinationValidator = new Func<Int64[], bool>
(
delegate(Int64[] instanceCombination)
{
bool result = true;
//filter out if both mobile phones are identical
if (instanceCombination[0] == instanceCombination[1])
{
result = false;
}
return result;
}
);
container.BuildPossibilitiesMatrix();
for (Int64 i = 0; i <= container.InstancesCombinationsMaxRowIndex; i++)
{
if (container.CombinationsExist)
{
for (Int64 k = 0; k <= container.InstancesCombinationsMaxColumnIndex; k++)
{
string color1 = colors[container[i, k, 0]];
string brand1 = brands[container[i, k, 1]];
string os1 = os[container[i, k, 2]];
rtxtOutput.Text += string.Format(CultureInfo.InvariantCulture, "[{0},{1},{2}]", color1, brand1, os1) + ((k != container.InstancesCombinationsMaxColumnIndex) ? "\t" : string.Empty);
}
rtxtOutput.Text += Environment.NewLine;
}
}
MessageBox.Show(string.Format(CultureInfo.InvariantCulture, "{0} prize combinations are found.", container.InstancesCombinationsMaxRowIndex + 1));
}
}
}
So, after using the library to calculate all possibilities of the problem described above then running the test application, we will get the results as in the image below.
Notes:
Please keep in mind that if the number of attributes and instances are too big this may cause an arithmetic overflow.
[Update] This library is already used on Application To Generate Combined Images Of All Image-Categories Possible Combinations
That's it. You can download the code from here
Hope you find this library useful.
Goodbye.
