String iteration generator?

Questions & Answers
1

Hey.

I am working on a project to make a code iteration generator. So, you’d input a string of, say, “xxy” and the code will give you all the possible combinations of that string. So, “yxx, xyx, xxy”

I have worked out this so far:
The string, in this case is “xxy.”

n = possible combinations

i = string length

∂i = number of different letters in the string / i

Therefore, n = i^(∂i) different possibilities?

(The above is now incorrect)

I did some manual combination checking, and when there are 3 different letters and three spaces available in the string, there would be 3^2 - 4 = 5 different possibilities.

( four repetitions in my working )

My working was:

x o y | [o x y] | y x o

o x y | [x o y] | [x y o]

o y x | x y o | [x o y]

so, a formula for finding the total combinations would be great as well… cuz mine was wrong.

Now, what I need is a formula to apply within a for( ) loop which would generate the possibilities, assuming I got the ∂i stuff right…

So, for every run through the loop, it’d apply the formula, and add a letter to the output string based on the combinations available?

My code thus far is:

#pragma strict

var inputCode : String; 
var output : String; 

private var running : boolean;

function Start()
{
	inputCode = "";
	output = "";
	running = false; 
}

function OnGUI() 
{
	GUI.BeginGroup(Rect(10,10,1000,1000));
	
	if(!running)
	{
		inputCode = GUI.TextArea(Rect(0,0,200,25), inputCode, 500);
	}
	else 
	{
		GUI.Label(Rect(0,0,200,25),"Generating...");
	}
	if((GUI.Button(Rect(0,30,200,25), "Generate")) && (!running))
	{
		Iterate(inputCode);
	}
	
	GUI.Label(Rect(0,60,2000,25), output);
	
	GUI.EndGroup();
}

function Iterate(ic : String)
{
	running = true;
	output = ""; 

    // find ∂i 
	
	for(var i = 0; i < ic.Length; i++)
	{
		output += ic*;  // replace with formula?*

  • }*

  • running = false;*
    }

I am at a loss with this, and would be amazing if someone could help. :slight_smile:
thank you
-F

2

I’m not a mathematician, but I believe this type of problem is a “Permutations with Duplicates”, or “Permutations with Identical Elements” (or some such), problem and there is a simple formula to determine the number of unique combinations for any given set.

Like @Bunny83 mentions, the total number of possible combinations with n elements = n!. To remove any duplicate combinations, you just have to divide n! by the permutations of the repeated elements. So in the case of “aaab”, ‘a’ is repeated 3 times, so the total unique combinations would be 4!/3! = 4. And “aabb” will give you 4!/(2!*2!) = 6. And “abcccdde” would give you 8!/(3!*2!) = 3360.

I found this site that explains the different types of Permutations pretty well - this type is (C) on the page.

Of course you still need your algorithm to generate the combinations, but at least you can verify your results…