Android Question how to compute different permutations of a string?

[tsteward]

I think thats an appropriate description.
I have a string eg "12212432"
User selects from 2 to 8 (subject to length of string) positions to swap around.
For this example user selects only 3 positions being psitions 2,4 &5

How would I reproduce this string swaping those characters around to get all possible permutations.
-2-12---
1x2xx432

Result
12221432
11222432
perhaps not the best example

I have no clue

 

[JonPM]

SubString2 ?

 

[tsteward]

SubString2 ?

That will allow me to grab or manipulate parts of the string but i'm not sure how to mix the appropriate parts in every possible combination.
So in the example above string1 = "2", string2 = "1", string 3 = "2"
now mix them up every way possible and write a routine to handle 4,5 or maybe even 6 characters and mix them all up and return all possibilities.

 

[JonPM]

To clarify, you show the user this string: "12345678"
The user then selects between 2 and 8 of the numbers.
Then you return all of the possible strings combinations of the selected strings swapped around? I.e. "12345687", " 12345768", "12345876", etc?

 

[tsteward]

I am a locksmith and these are the cuts of the key. A key may hav from 6 to 12 cuts. In my example I have chosen an 8 cut key.

So yes a string of say 8 digits is presented to the user.
The user will then select any where from 2 to all 8 position.
I then wish to present the user with all possibilities, shuffling around only the characters that they have chosen.

Selecting positions 3, 5, 6 as follows
12345678
Result
12346578
12645378
12643578
12543678
12546378

 

[JonPM]

Does it matter to you that if the user selects all 8 numbers there will be over 40,000 combinations? It may be useless to show this many to the user

 

[tsteward]

Agreed this many will be useless.
What I will do once I have collected all possibilities is compare each result against a database for the particular key series and filter out any that are not actual key bittings used by the particular vehicle's manufacturer.

The aim is to collect the bitting (cuts) used on the vehicle the locksmith is currently working on. The locksmith decides which cuts are in all locks on the vehicle. Selects those cuts to create a new code which must be a valid code as pre defined by the manufacturer. Then by swapping around the existing pins in the locks prevents the old key from working and cuts a new valid key. This enables the locksmith to not need keying kits for every vehicle out there because he is re-using whats already in the lock.

A Toyota Camry for example might have 8 pins in the ignition, 7 pins in the door but only 4 pins in the glove box. In the senario the locksmith selects the positions of the 4 pins in the glovebox and can effectivly rekey the vhicle supplying nothing but the new key. Enabling him maximum profit while still doing the job professionally.

 

[udg]

Hi tsteward,
unfortunately I'm on a train now so can't write any sample code, but maybe the following hint could help you.

start collecting the chars you need to shuffle and make a new string from them.
apply a permutation without repetition algorythm to the new string, yielding an array of "shuffled" strings
merge the resulting strings with the original one, substituting the chosen chars.

search the internet or eventually the forum for the permutation algorythm.

udg

 

[tsteward]

Ok I found a php example that I understand and works. Thinking I might pursue this and let the server do all the work rather than try to do it on the phone.
Especially since this is where the databases are anyway.

Awesome I have a direction to head, I'll see how I go.

Thanks

 

[stevel05]

Try this:

Dim Orig As String = "12212432"
    'To avoid having to cast String to int, we could start with Selection as an array of ints.
    Dim Selection As String = "245"
    Dim Result As StringBuilder
    Dim Results As List
    Dim Source,Target,sPos,tPos As String
 
    Results.Initialize
    'Store the original order (if required)
    Results.Add(Orig)
 
    For i = 0 To Selection.Length - 1
        sPos = Selection.CharAt(i)
        sPos = sPos -1
        Source = Orig.CharAt(sPos)

        For j = i To Selection.Length - 1
            Result.Initialize
            Result.Append(Orig)
            If i = j Then Continue
            tPos = Selection.CharAt(j)
            tPos = tPos - 1
            Target = Orig.CharAt(tPos)
            Result.Remove(sPos,sPos+1)
            Result.Insert(sPos,Target)
            Result.Remove(tPos,tPos+1)
            Result.Insert(tPos,Source)
            Log("Debug:")
            Log((sPos + 1) &":"&Source & " : " & (tPos + 1) & ":" & Target)
            'Store the result if unique. To avoid doing a comparison we could add directly to a map as Key
            'We would then only get unique entries by default
            If Results.IndexOf(Result.ToString) = -1 Then
                Results.Add(Result.ToString)
                Log("Unique : "& Result & " Stored")
            Else
                Log("Duplicate: " & Result & " Not Stored")
            End If
        Next
    Next
    Log("Results :")
    For Each R As String In Results
        Log(R)
    Next

 

[tsteward]

Hey Stevel05, thenks for your code. I'm gonna look at doing it in php but may well come back to this yet.

Thank you

 

[stevel05]

No problem, I did see your post but as I had finished it I thought I'd post it anyway. It may be useful.

 

[DonManfred]

at doing it in php

http://stackoverflow.com/questions/5506888/permutations-all-possible-sets-of-numbers

pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8)));

function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        print join(' ', $perms) . "\n";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

 

[DonManfred]

Maybe this can help?