Posts: 15
Threads: 7
Joined: Aug 2022
Reputation:
1
Say I have a string variable abcd$. The letters in the variable can be arranged 4 factorial or 4x3x2x1 different ways. How can I produce every combination? Find Len(abcd$) then a for/next loop Len factorial times, but what inside the loop? I'm at a loss here.
Posts: 922
Threads: 44
Joined: May 2022
Reputation:
18
04-24-2024, 11:32 AM
(This post was last modified: 04-24-2024, 11:42 AM by Kernelpanic.)
(04-24-2024, 11:14 AM)Circlotron Wrote: Say I have a string variable abcd$. The letters in the variable can be arranged 4 factorial or 4x3x2x1 different ways. How can I produce every combination? Find Len(abcd$) then a for/next loop Len factorial times, but what inside the loop? I'm at a loss here. ![Huh Huh](https://qb64phoenix.com/forum/images/smilies/huh.png) This is the calculation of the factorial: n!
Code: (Select All)
'Fakultaet iterativ mit FOR-Schleife - 11. Feb. 2023
$Console:Only
Option _Explicit
Declare Function Fakultaet(n As Integer) As _Integer64
Dim As Integer n
Locate 2, 3
Print "Iterative Berechnung der Fakultaet - (n!)"
Locate 4, 3
Input "Fakultaet von (n): ", n
Locate 5, 3
Print Using "Die Fakultaet von ### ist: ###,###,###"; n, Fakultaet(n)
End 'Hauptprogramm
Function Fakultaet (n As Integer)
Dim As _Integer64 fakul
Dim As Integer i
fakul = 1
For i = 1 To n
fakul = fakul * i
Next
Fakultaet = fakul
Oder in Julia:
Posts: 15
Threads: 7
Joined: Aug 2022
Reputation:
1
Thanks for that. In the meantime I realised I was asking the wrong question. I'll start a new thread.
Posts: 3,549
Threads: 165
Joined: Apr 2022
Reputation:
172
maybe you want every permutation, not combination as there are 4! permutations to abcd letters.
b = b + ...
Posts: 2,356
Threads: 287
Joined: Apr 2022
Reputation:
180
Code: (Select All)
ReDim Shared WordList(0) As String
FactorIt "1234", ""
For i = 1 To UBound(WordList)
Print WordList(i),
Next
Sub FactorIt (word$, seed$)
For i = 1 To Len(word$)
seed1$ = seed$ + Mid$(word$, i, 1)
w$ = Left$(word$, i - 1) + Mid$(word$, i + 1)
For k = 1 To UBound(WordList)
If WordList(k) = seed1$ + w$ Then Exit For
Next
If k > UBound(WordList) Then
ReDim _Preserve WordList(k) As String
WordList(k) = seed1$ + w$
End If
FactorIt w$, seed1$
Next
End Sub
FactorIt above generates a list of values, removing duplicates for you. For example, "goo" has two "o"s, so it can only generate "goo", "ogo", "oog", and a few of those in duplicate which we don't count.
Posts: 1,847
Threads: 190
Joined: Apr 2022
Reputation:
88
I tried running the string "THIS" in this FreeBASIC permutation algorithm, but it got stuck in an endless loop...
Code: (Select All)
Print "Find the permutations of the word: THIS."
a$ = "THIS"
Sleep 5
Do
a = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 4
b = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 2
c = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 3
d = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 1
Print Mid$(a$, a, 1) + Mid$(a$, b, 1) + Mid$(a$, c, 1) + Mid$(a$, d, 1); " ";
_Delay .02
Loop Until perm = 24
I'm thinking about emailing it to Clippy, as a screen saver.
Pete
Posts: 616
Threads: 89
Joined: Apr 2022
Reputation:
20
04-25-2024, 11:10 PM
(This post was last modified: 04-25-2024, 11:13 PM by PhilOfPerth.)
(04-24-2024, 11:14 AM)Circlotron Wrote: Say I have a string variable abcd$. The letters in the variable can be arranged 4 factorial or 4x3x2x1 different ways. How can I produce every combination? Find Len(abcd$) then a for/next loop Len factorial times, but what inside the loop? I'm at a loss here. ![Huh Huh](https://qb64phoenix.com/forum/images/smilies/huh.png)
I' m currently working on a similar problem for one of my games (hope it's not the same game!) so I'll be interested to see what comes up from the gurus here.
(04-25-2024, 02:13 AM)Pete Wrote: I tried running the string "THIS" in this FreeBASIC permutation algorithm, but it got stuck in an endless loop...
Code: (Select All)
Print "Find the permutations of the word: THIS."
a$ = "THIS"
Sleep 5
Do
a = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 4
b = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 2
c = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 3
d = (Rnd * 3 Mod 4) * 365 / 4 ^ 7 + 1
Print Mid$(a$, a, 1) + Mid$(a$, b, 1) + Mid$(a$, c, 1) + Mid$(a$, d, 1); " ";
_Delay .02
Loop Until perm = 24
I'm thinking about emailing it to Clippy, as a screen saver.
Pete ![Big Grin Big Grin](https://qb64phoenix.com/forum/images/smilies/biggrin.png)
Wow, wonder why that happens!
Posts: 616
Threads: 89
Joined: Apr 2022
Reputation:
20
04-25-2024, 11:19 PM
(This post was last modified: 04-26-2024, 01:56 AM by PhilOfPerth.)
(04-24-2024, 07:41 PM)SMcNeill Wrote: Code: (Select All)
ReDim Shared WordList(0) As String
FactorIt "1234", ""
For i = 1 To UBound(WordList)
Print WordList(i),
Next
Sub FactorIt (word$, seed$)
For i = 1 To Len(word$)
seed1$ = seed$ + Mid$(word$, i, 1)
w$ = Left$(word$, i - 1) + Mid$(word$, i + 1)
For k = 1 To UBound(WordList)
If WordList(k) = seed1$ + w$ Then Exit For
Next
If k > UBound(WordList) Then
ReDim _Preserve WordList(k) As String
WordList(k) = seed1$ + w$
End If
FactorIt w$, seed1$
Next
End Sub
FactorIt above generates a list of values, removing duplicates for you. For example, "goo" has two "o"s, so it can only generate "goo", "ogo", "oog", and a few of those in duplicate which we don't count.
Ahah! That's a (reasonably) simple solution to a problem I'm wrestling with at the moment! I had written a factorial-ising routine, but it was way too bulky and slow to be useful. I'll try to adapt this into my language ("dumb it down") and use it!
Edit: This worked when I used alpha chars, which is what I want) to do), but when I used anything longer than 7 characters, it gave no result.
Edit2: I was able to get results when I added this before the last Next, and remove the Print wordlist$(i)
Print wordlist(k);" ";
It's still very slow for more than 7 chars, but that may be enough (for mine, anyway). 87 sec for 8 characters.
Posts: 3,549
Threads: 165
Joined: Apr 2022
Reputation:
172
04-26-2024, 02:17 PM
(This post was last modified: 04-26-2024, 02:21 PM by bplus.)
Quote:Edit: This worked when I used alpha chars, which is what I want) to do), but when I used anything longer than 7 characters, it gave no result.
these are permutations, there are n! for n elements
N! = 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, ....
that sequence expands faster than any x^n ie expedentially plus!
you propably didn't get results because you didn't wait long enough plus real easy to go beyond the limits of the type fairly quickly.
that routine steve provided i think was better than what i had, except maybe the non recursive one?
i filed the data for 10 letters or digits so i could use a substitution technique for 10 of anything without recalculating permutaions of 10 things because it takes so long.
b = b + ...
Posts: 616
Threads: 89
Joined: Apr 2022
Reputation:
20
At the risk of hijacking Circlotron's post further, ![Big Grin Big Grin](https://qb64phoenix.com/forum/images/smilies/biggrin.png) thanks @bplus. I was aware of the permutatins thing and its associated problem with expansion, but couldn't see a way around it.
Not sure what you meant in your last line, about filing the data... could you elaborate a little? It sounds interesting.
|