Android Question Permutations of a String

[Ohanian]

Hi,

I'm looking for a fast Permutation lib or code snippet with ability to specify the length of generated elements.

Here’s a lib but it generates fixed elements based on the referenced string that contains all characters of the referenced string.

Unfortunate the lib is old and the source code is not available.

Thanks in advance.

 

[sorex]

you mean like this?

Sub Process_Globals
 Private fx As JFX
 Private MainForm As Form
 Dim permutations As List
End Sub

Sub AppStart (Form1 As Form, Args() As String)
 MainForm = Form1
 MainForm.Show

 permutations.Initialize
 permutate("","abcd",5)
 Log(permutations)
End Sub

Sub permutate(prefix As String, str As String,maxlen As Int)
 If permutations.Size=maxlen Then Return
 If str.Length=0 Then permutations.Add(prefix)
 For i = 0 To str.Length-1
  permutate( prefix & str.charAt(i), str.substring2(0,i) & str.substring2(i+1,str.Length),maxlen)
 Next
End Sub

output: (ArrayList) [abcd, abdc, acbd, acdb, adbc]

 

[Ohanian]

you mean like this?

Sub Process_Globals
 Private fx As JFX
 Private MainForm As Form
 Dim permutations As List
End Sub

Sub AppStart (Form1 As Form, Args() As String)
 MainForm = Form1
 MainForm.Show

 permutations.Initialize
 permutate("","abcd",5)
 Log(permutations)
End Sub

Sub permutate(prefix As String, str As String,maxlen As Int)
 If permutations.Size=maxlen Then Return
 If str.Length=0 Then permutations.Add(prefix)
 For i = 0 To str.Length-1
  permutate( prefix & str.charAt(i), str.substring2(0,i) & str.substring2(i+1,str.Length),maxlen)
 Next
End Sub

output: (ArrayList) [abcd, abdc, acbd, acdb, adbc]

Hi,

Not exactly

The maxlen parameter in your code is the max count of the generated elements, but what I want is to set the length of generated element, here’s a sample:

My reference string is:

(‘a’,’b’,’c’,’d’)

I need a list of all possible combination strings that can be made with these letters with length condition of 2, like:

ab, cd, db, da, …

 

[sorex]

you can always mod my example to work like that

I'll have a look at it later.

 

[sorex]

not really optimized to the bone but I guess this is what you want

    permutations.Initialize
    permutations.Clear
    permutate("abcd",2)
 Log(permutations)
 Log("----------------")
    permutations.Clear
    permutate("abcd",3)
  
 Log(permutations)
End Sub

Sub permutate(str As String,maxlen As Int)
   Dim t As String
   Dim p,c As Int
   For x=0 To str.Length-1
       For y=x+1 To x+str.Length-1
           c=0
           t=str.CharAt(x)
           Do While t.Length<maxlen
               p=(y+c) Mod str.Length
               If p<>x Then   t=t & str.CharAt(p)
               c=c+1
           Loop
           permutations.Add(t)
       Next
   Next
End Sub

(ArrayList) [ab, ac, ad, bc, bd, ba, cd, ca, cb, da, db, dc]
----------------
(ArrayList) [abc, acd, adb, bcd, bda, bac, cda, cab, cbd, dab, dbc, dca]

 

[sorex]

I just see that it's not 100% right. it's only doing it in forward direction. But you get the idea.

 

[sorex]

Sub permutate(prefix As String, str As String,maxlen As Int)
    If str.Length=0 And permutations.IndexOf(prefix.SubString2(0,maxlen))=-1 Then permutations.add(prefix.SubString2(0,maxlen))
    For i = 0 To str.Length-1
        permutate( prefix & str.charAt(i), str.substring2(0,i) & str.substring2(i+1,str.Length),maxlen)
    Next
End Sub

(ArrayList) [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]
----------------
(ArrayList) [abc, abd, acb, acd, adb, adc, bac, bad, bca, bcd, bda, bdc, cab, cad, cba, cbd, cda, cdb, dab, dac, dba, dbc, dca, dcb]

 

[William Lancee]

I needed something like this recently. I have posted a solution today as a code snippet. The solution is for unique combinations but when you need pairs of objects they can easily be reversed for a complete set of pairs.

https://www.b4x.com/android/forum/threads/unique-combinations-of-m-objects-from-a-set-of-n.99463/​