Android Question help me make my code shorter

ilan

Expert
Licensed User
i am working a tool to get all possibilities of x number from x numbers like lotto.

this is my code but i dont like the multi for ... loops and also if i would like to calculte a different amount of numbers from x numbers i cannot do it with this code i need to change the code for it and i would like it to be more flexible.

B4X:
Sub runPos
    Dim list1 As List
    list1.Initialize
    
    Dim highNumber As Int = 9
    Dim toCollectNumber As Int = 6
    Dim numberStr As String = "" 'ignore
    
    'start   //calculate possibilities
    Dim possibilities As Int = 1
    For z = 0 To toCollectNumber - 1
        possibilities = possibilities * (highNumber - z)
    Next
    Log(factorial(toCollectNumber))
    Log(possibilities / factorial(toCollectNumber))
     'end
    
    'get all possibilities (STRING)
    For i = 1 To highNumber
        For j = 2 To highNumber
            For k = 3 To highNumber
                For l = 4 To highNumber
                    For m = 5 To highNumber
                        For n = 6 To highNumber
                            Dim item As String = "|" & i & "|" & j & "|" & k & "|" & l & "|" & m & "|" & n & "|"
                            Dim found As Boolean = False
                            For Each line As String In list1
                                If line.Contains("|" & i & "|") And line.Contains("|" & j & "|") And line.Contains("|" & k & "|") And line.Contains("|" & l & "|") And line.Contains("|" & m & "|") And line.Contains("|" & n & "|") Then
                                    found = True
                                    Exit
                                End If
                            Next
                            If found Then Continue
                            list1.Add(item)
                            'numberStr = numberStr & item & CRLF
                        Next
                    Next
                Next
            Next
        Next
    Next
 
    Log("list size: " & list1.Size)
    'fx.Clipboard.SetString(numberStr)
End Sub

Sub factorial(number As Int) As Int
    Dim returnNr As Int = number
    Do Until number <= 1
        number = number - 1
        returnNr = returnNr * number
    Loop
    Return returnNr
End Sub
 

Erel

Administrator
Staff member
Licensed User
I assume that no number should be repeated.
If you know the permutations of n-1 then you just need to insert the last number in all possible positions:
B4X:
Sub AppStart (Args() As String)
   Dim p As List = Perms(Array(1, 2, 3, 4, 5))
   Log(p.Size)
   Log(p)
End Sub

Sub Perms(numbers As List) As List
   Dim res As List
   res.Initialize
   If numbers.Size = 1 Then
       res.Add(numbers.Get(0))
       Return Array(res)
   End If
   Dim n As Int = numbers.Get(0)
   Dim temp As List
   temp.Initialize
   For i2 = 1 To numbers.Size - 1 'all except first
       temp.Add(numbers.Get(i2))
   Next
   Dim PermsN1 As List = Perms(temp)
   For Each p As List In PermsN1
       For i2 = 0 To p.Size
           Dim NewPerm As List
           NewPerm.Initialize
           NewPerm.AddAll(p)
           NewPerm.InsertAt(i2, n)
           res.Add(NewPerm)
       Next
   Next
   Return res
End Sub
 

ilan

Expert
Licensed User
very nice erel but what i am doing in my code is i want to get all possibilities for x number from x numbers for example.

in a lotto game we have 36 balls. we choose only 6 balls from those 36. now to get all possible combinations we do it like this.

first ball is a chance of 1/36, second is 1/35,...

so we do 36 * 35 * 34 * 33 * 32 * 31 = 1402410240 possible combination

BUT because we dont care is a number combination repeats in different order like

123 or 321 is the same so we take the result and divide by n! of the selected balls number (6)

1402410240 / factorial(6) = 1947792

so to get 6 balls from 36 we have 1947792 combinations (order doesnot matter)

and in my code i am doing it but i would like to avoid all those 6 loops and also if i want to know all combinations only for 3 balls from 36 i have to change my code.

i am thinking of a solution for a while but still have not found a shorter way to calculate it.

thank you, ilan

EDIT: http://www.webmath.com/lottery.html
 

Erel

Administrator
Staff member
Licensed User
B4X:
Sub AppStart (Args() As String)
   Dim r As List = GetXFromNumbers(3, Array(1, 2, 3, 4, 5, 6))
   Log(r.Size)
   Log(r)
   
End Sub

Sub GetXFromNumbers(x As Int, numbers As List) As List
   Dim res As List
   res.Initialize
   'stop condition
   If x = 1 Then
       For Each n As Int In numbers
           Dim r As List
           r.Initialize
           r.Add(n)
           res.Add(r)           
       Next
       Return res
   End If
   
   For i = 0 To numbers.Size - x
       Dim n As Int = numbers.Get(i)
       Dim TempList As List
       TempList.Initialize
       For i2 = i + 1 To numbers.Size - 1
           TempList.Add(numbers.Get(i2))
       Next
       Dim g As List = GetXFromNumbers(x - 1, TempList)
       For Each resn1 As List In g
           Dim r As List
           r.Initialize
           r.Add(n)
           r.AddAll(resn1)
           res.Add(r)
       Next
   Next
   Return res
End Sub
 

ilan

Expert
Licensed User
B4X:
Sub AppStart (Args() As String)
   Dim r As List = GetXFromNumbers(3, Array(1, 2, 3, 4, 5, 6))
   Log(r.Size)
   Log(r)
  
End Sub

Sub GetXFromNumbers(x As Int, numbers As List) As List
   Dim res As List
   res.Initialize
   'stop condition
   If x = 1 Then
       For Each n As Int In numbers
           Dim r As List
           r.Initialize
           r.Add(n)
           res.Add(r)          
       Next
       Return res
   End If
  
   For i = 0 To numbers.Size - x
       Dim n As Int = numbers.Get(i)
       Dim TempList As List
       TempList.Initialize
       For i2 = i + 1 To numbers.Size - 1
           TempList.Add(numbers.Get(i2))
       Next
       Dim g As List = GetXFromNumbers(x - 1, TempList)
       For Each resn1 As List In g
           Dim r As List
           r.Initialize
           r.Add(n)
           r.AddAll(resn1)
           res.Add(r)
       Next
   Next
   Return res
End Sub
shock.png


YOU ARE A GENIUS EREL!

i still have not understood the function but will study it. big big wow!!! thank you :)
 

Erel

Administrator
Staff member
Licensed User
It is a bit difficult to explain but I'll try.

Lets say that we know how to solve GetXFromNumbers where x = 2 and we need to solve it for x = 3.
The numbers are 1, 2, 3, 4, 5, 6.
As the order of numbers doesn't matter, we always keep the numbers in the same order.
First step is to find all solutions where 1 is the first number:
1, 2, 3
1, 2, 4
1, 2, 5
1, 2, 6
1, 3, 3
...

This is equivalent to solving: GetXFromNumbers (2, Array(2, 3, 4, 5, 6))
And then add 1 as the first item of each result.

All solutions are the union of:
1 is the first number, GetXFromNumbers (2, Array(2, 3, 4, 5, 6))
2 is the first number, GetXFromNumbers (2, Array(3, 4, 5, 6))
3, GetXFromNumbers (2, Array(4, 5, 6))
4, GetXFromNumbers (2, Array(5, 6))

This is the algorithm behind the code above.
 
Top