Gammon Forum

//should've named this something else.
//this function is used in a loop and is passed the count(iteration)
//and a reference to an absolute path and pointer array.
//it then modifies the pointer array that makes it possible
//to get all combinations(without repeat) of a given set.
//In this sample situation, it is given a path of [h1,h2,h3]
//and a pointer array of [0,1,2]. give the combinations
//h1,h2,h3
//h1,h3,h2
//h2,h3,h1
//h2,h1,h3
//h3,h1,h2
//h3,h2,h1
//some math to notice. As said before, the amount of combinations
//without repeat is a factorial of the amount of elements. In this case
//there is 3 elements: h1,h2,h3. factorial of 3 is 3 * 2 * 1 = 6.
//also note that the total amount of any element in any column is 2 in this case.
//I got a general formula of (exlemation mark is used to say factorial) -
//(number of elements)! / number of elements. This will give the given amount
//of any element in a column. 6/3 = 2.
function possibleCombinations(iteration, rAry, rPath) {
	//prevents some divide by zero errors.
	if (iteration != 0) {
		//pos = current position...starting right to left.
		var pos;
		for (var pCount = 0;pCount < rPath.length - 1;pCount++) {
			//-1 because we don't like out of range errors *sage nod*.
			pos = rPath.length - 1 - pCount;
			//posAllowed give me(in this case) the 6/3 = 2 thing.
			//the way this logic works is if it's at position 1 or 2(right to left)
			//it will just switch position 1 and 2. This works out because position
			//1 and 2 are the last elements to be checked for switching. If any positions
			//are switched before it, then it returns out of the function...this function
			//only switches once in any given iteration.
			if (iteration % posAllowed(pos) == 0) {
				var temp;//holding variable.
				//this checks if it's in position 2 and switches 1 and 2 if it is.
				if (rPath.length - pCount == 2) {
					temp =rAry[pCount];
					rAry[pCount] = rAry[pCount + 1];
					rAry[pCount + 1] = temp;
				} else {//else it's in position 3 or greater.				
					temp = rAry[pCount];
					rAry[pCount] += 1;
					//this searches for the position of the element that is
					//pointing at the element it needs to switch to.
					//so, at h1,h3,h2 rAry is [0,2,1] and rAry[0] needs to be incremented
					//to 1, so it searches for the position that holds one and makes it 0.
					//( in the case that the position is deeper, which would happen in 4+
					//element sets, it increments to the next available value isn't behind it.
					if (rAry[pCount] >= rPath.length) {
						var fCount = 0,increment = 0;
						while (fCount < pCount) {
							if (rAry[fCount] == increment) {
								increment++;
								fCount = 0;
							}
							fCount++;
						}
						rAry[pCount] = increment;
					}
					//search for pointer with the same value.
					var sCount = 0;
					var sBool = false;
					while (sCount < rAry.length && sBool == false) {
						if (rAry[sCount] == rAry[pCount] && sCount != pCount) {
							if (sCount < pCount) {
								rAry[pCount] += 1;
								sCount = 0;
							} else {
								rAry[sCount] = temp;
								sBool = true;
							}
						} else {
							sCount++;
						}
					}
				}
				return;
			}
		}
	}
}

function posAllowed(pos) {
	pos += 1;
	//this is the total amount of times an element
	//is allowed to show in any given column.
	return Utilities.factorial(pos)/pos;
}
function pathCheck(rAry,rPath) {
	var c = 0, i = 0, k = 0;
	var cPath, pPath;
	var missBool = false, checkPath;
	var currentSet;
	while (c < rPath.length && missBool == false) {
		currentSet = hSet[rPath[rAry[c]]];
		//not possible to produce empty sets if there's not even enough
		//healing methods to remove all elements in it.
		//so, if current amount of elements is <= the amount of methods before the current methods position.
		if (currentSet.size <= rPath.length - (rPath.length - c)) {
			cPath = currentSet.elements.concat();
			pPath = [];
			//populate pointers
			for (var j = 0;j < cPath.length;j++) {
				pPath.push(j);
			}
			//while i < the amount of permutations of the current healing method.
			while (i < Utilities.factorial(currentSet.size) && missBool == false) {
				possibleCombinations(i,pPath,cPath);
				testing(pPath,cPath);
				checkPath = true;
				while (k < cPath.length && checkPath == true) {
					if (!(cPath[pPath[k]] in hSet[rPath[rAry[c]]])) {
						checkPath = false;
					}
					k++;
				}
				if (checkPath == true) {
					missBool = true;
				}
				i++;
			}
		}
		c++;
	}
	return missBool;
}

function test() {
	world.Note("<---begin test--->");
	var h1 = new Utilities.Set([{name:"a1",value:"a1"},
								{name:"a2",value:"a2"},
								{name:"a3",value:"a3"}
								]);
	var h2 = new Utilities.Set([{name:"a1",value:"a1"},
								{name:"a2",value:"a2"},
								{name:"a3",value:"a3"}
								]);
	var h3 = new Utilities.Set([{name:"a1",value:"a1"},
								{name:"a2",value:"a2"}
								]);
	var h4 = new Utilities.Set([{name:"a1",value:"a1"},
								{name:"a2",value:"a2"},
								{name:"a3",value:"a3"},
								{name:"a4",value:"a4"}
								]);
	var hSet = new Utilities.Set([{name:"h1",value:h1},
								  {name:"h2",value:h2},
								  {name:"h3",value:h3}//,
								  //{name:"h4",value:h4}
								 ]);								 
	//how many combinations there are without repeats.
	var permutations = Utilities.factorial(hSet.size);

	//gets a copy of the array elements held in a set object.
	//this is used as an absolute reference for wrkArray.
	var path = hSet.elements.concat();
	//wrkArray holds pointers to relative position.
	//i.e. path ='s ["H1","H2","H3"];
	//if wrkArray = [0,2,1] then
	//it would make a path of: H1,H3,H2
	var wrkArray = [];
	//initializes wrkArray to 0,1,2...
	for (var pc = 0;pc < path.length;pc++) {
		wrkArray.push(pc);
	}
	//a display function for testing.
	function testing(rAry,rPath) {
		var str = "path: " + rPath[rAry[0]];
		for (var tCount = 1;tCount < rPath.length;tCount++){
			str += ", " + rPath[rAry[tCount]];
		}
		world.note(str);
	}
	for (var c = 0;c < permutations;c++) {
		possibleCombinations(c,wrkArray,path);
		if (!pathCheck(wrkArray,path)) {
			testing(wrkArray,path);
			world.Note ("is a path that doesn't miss");
			c = permutations;
		}
	}
	world.Note("<-----end test------>");
}