Looking for unique number of Base X

Is there a source out there for files that have all unique numbers for different number bases?

I generated my own for base 10 by having 10 nested loops and a humungous IF statement that checked for uniqueness each time the inmost loop incremented. The resulting 10 digit number did not contain a duplicate number. If none of the numbers were dup’d, I’d write it to a file. But going up the Base 12 increases that effort immensely. At least in computer “crank” time. Is there an efficient way to generate all numbers of a certain base with no repeated digits in the string?

It seems something like that - the files of unique numbers for each number base - should be living on the internet somewhere.

For clarity, with Base 10, this number would be what I wanted 3572109864
This number would not: 3572103864 because there are two “3’s”.

I’m looking for the same thing but with Base 12 numbers 0123456789AB

Or a more efficient algorithm besides 12 nested loops running from 0 to 11, converting 10 and 11 to A and B and checking that no number has a repeated 12 digit number has repeated “digits” - A and B are digits so each number is converted to text and each element is compared to all the others.

Perhaps

Dim n() As String
For i As Integer = 0 To 9
  n.Add(i.ToString)
Next i

n.Add("A")
n.Add("B")
n.Shuffle

Var s As String = String.FromArray(n, "")
1 Like

Thank you, Wayne. I’m a little slow on code so I might be wrong but it appears that your example generates only one number string. What, in that example, assures the generation of all unique - and by unique I mean no duplicated digits - numbers. I imagine that shuffle scambles the string but unless there’s some “no duplicates” guarantee, with shuffle, it could hand me the same number with multiple iterations.

I believe the count of numbers I’m looking for is the factorial of the base. So Base 10’s file would contain 3628800 numbers. The Base 12 file of numbers without duplicate digits would contain 12 factorial numbers or 479001600 different numbers, none of which contain a duplicated digit.

I’ll add this separately in case it wasn’t clear - note, what do I click to edit my posts. I didn’t see an icon for that? I see the pencil at the bottom of this post. I guess I’m used to a longer duration window for making changes.

When I say all unique numbers, I’m looking for a 10 digit number for BASE 10 - not a number like “238” And when I say unique, I mean none of the digits in the number are duplicated as per my initial post.

I did generate a file of all numbers fitting my criteria for BASE 10 in a very brute force way. So I’m looking for something to do the same thing for any base - say up to Base 15. in a more elegant - and by elegant I mean faster - fashion. Or, such a file might be out there on the internet. I’ve Googled for it a few times but either it doesn’t exist or I haven’t hit the right combination of key words for the search.

Norman suggested this on the other forum:

2 Likes

What’s the representation for beyond base 36 ?
0-9 and A-Z only go so far…

Use a-z for 10-36 and A-Z for 37-62. Add + and / and you’ve got base-64. I don’t think there’s a widely accepted set of symbols for beyond that.

My interest would only go up to BASE 15 - Hex. But for now, a BASE 12 solution would be fine. I’ll look at that Heaps Algorithm; thank you.

Does the Shuffle command generate all possibilities or does it do a random scramble and hand you only one?

Base 16 - Hex :smiley: 0-15

Yes - my mistake :hot_face:. I am really just focusing on BASE 12 now.

I wish the forum could be a little more generous with their edit interval window. But then again, we need to learn to check our code - even if it’s “comments”.

The Heap Algorithm suggested above looks great. Though the examples I’ve found use numbers, it appears the method involves swapping array elements so it don’t make no never mind if those array elements are numbers or characters. So I could load it up with 0 - B and let’er rip. Need to test a small sample first - make sure I remove delimiters so those elements concatenate back to a number. And write to a file of course.

If I click the Solution box on the Heap Algorithm suggestion, does it close the tread or will the tread remain open?

It remains open for 6 month, but it will drift away to the past soon.

Thank you Rick. Andrew’s mention of Norman’s suggestion of Heap’s Algorithm for generating permutations seems to be a solution or at least a viable direction to pursue.

Thank you all for your suggestions.

If speed isn’t your concern, you can adapt the code to use strings rather than arrays.

Hi Paul,
maybe this will help you.
Open a new desktop project
In the window insert the property
total As Integer
insert the method “permuta” with the following code:

    Public Sub permuta(t As String, s As String)
   Var s0, si As string
   Var i As integer
    If s.Length = 1 Then
        total = total + 1
       Listbox1.AddRow(total.ToString, t + s)
   Else
        permuta(t + s.Left(1), s.Middle(1))
        For i = 2 to s.Length
           s0 = s.Left(1)
           si = s.Middle(i-1, 1)
            s = si + If(i > 2, s.Middle(1, i-2), "") + s0 + If(i + 1 <= s.Length, s.Middle(i), "")
            permuta(t + s.Left(1), s.Middle(1))
       Next
     End If
End Sub

In the windows1 add a TextField, a Button, a ListBox with 2 columns

In the event pressed of Button1 insert the following code:

    Sub Pressed() Handles Pressed
  If TextField1.Text = "" Then
    MessageBox("Insert string")
  Else
    total=0
    Listbox1.RemoveAllRows
       
    permuta("", TextField1.Text)
    
  End If
  
End Sub

The program generates all possible permutations of the characters of the inserted string. Attention: the inserted characters must all be distinct because we are considering simple permutations (without repeated characters).
Consider that the number of permutations of n characters is
n! = n*(n-1)*(n-2)* ... *3*2*1
this value grows very quickly as n increases, e.g.

 5! = 120
10! = 3,628,800
15! = 1,307,674,368,000

and you could easily exceed what are the limits of pc or xojo. I don’t know what is the maximum number of recursive calls of a function or the maximum number of rows in a listbox.
Also the time required for processing can become excessive.
Regards

Translated with www.DeepL.com/Translator (free version)

@Paul_Chance
Hi Paul,
the one I proposed is a recursive version to compute permutations. I remember also studying an “Iterative algorithm for generating permutations in lexicographic order”,
as soon as I find my old notes, I will try to send you the iterative version of the algorithm as well.
Regards.

Domenico, thank you for the example code. When I started down this path, I figured there were N choices for the first number, N-1 choices for the second, N-2 for the third … and so it would be N! numbers.

I brute-forced it with Base 10 and an ugly IF statement to eliminate numbers with duplicate digits but just knew there had to be a better way.

Because I’ll be going to Base 12, I’ll need to deal with characters.

I do prefer iterative rather than recursive - probably just because of my generation (age). despite a few visits to canyons. I’m not comfortable calling myself.

I’ll set up the recursion and if you find the iterative method, please pass it along.
Thank you again for easing my coding burden.

Hi Paul, here is the iterative version of the algorithm to detemine permutations of n elements.
Open a new desktop project
In the window insert the property

total As Integer

add a second property

p() As String

insert the method “permuta” with the following code:


Public Sub permuta()
  // Implementazione dell'algoritmo di Johnson-Trotter
  // Metodo iterativo per calcolare le permutazioni di n elementi distinti
  
  var flag As Boolean
  var j, n, s, q, i As integer
  var c(), d() As integer
  var temp As String
  
  n=p.Count
  
  // Inizializza il vettore degli scambi c() con tutti gli elementi a 0
  // Inizializza il vettore delle direzioni d() con tutti gli elementi a 1
  for i=0 to n-1
    c.Add(0)
    d.Add(1)
  Next
  
  do
    flag = True
    j = n-1
    s = 0
    
    do
      q = c(j)+d(j)
      if (q=1 And j=0) Then Return   //   <-- exit -->
      if (q>=0 And q<>(j+1)) then
        'swap ================
        temp = p(j-c(j)+s)
        p(j-c(j)+s) = p(j-q+s)
        p(j-q+s) = temp
        '=====================
        c(j) = q
        flag = False
      else
        if (q=j+1) Then s=s+1
        if (q<0 or q=(j+1)) Then
          d(j) = (-1)*d(j)
          j = j-1
        end if
      end if
      if flag=False Then exit
    loop 
    '================
    mostraElemento()
    '================
  loop 
End Sub

add a second method “mostraElemento” with the following code:


Public Sub mostraElemento()
  Var k As integer     
  var element As String
  
  // Crea l'elemento della permutazione
  element=""
  for k = 0 to p.Count-1
    element=element+p(k)
  next
  
  // Visualizza la permutazione nella ListBox
  // (è possibile salvarla in un database oppure in un file di testo)
  total=total+1
  Listbox1.AddRow(total.ToString, element)
  
End Sub

In the event pressed of Button1 insert the following code:


Sub Pressed() Handles Pressed
  If TextField1.Text = "" Then
    MessageBox("Insert string")
  Else
    total=0
    Listbox1.RemoveAllRows
    
    // inizializza vettore p - ogni elemento è un carattere della stringa inserita
    p.RemoveAll
    p=TextField1.Text.Split("")
    
    mostraElemento() // Mostra il primo elemento (la stringa inserita nel TextField)
    
    permuta()
    
  End If
End Sub

Modify the “mostraElemento” method to save the result in a text file or database, instead of showing it in a listbox (because I think it can not contain 12!=479,001,600 lines).

Sorry for my English, I hope I have been helpful, I wish you good work

Hi Domenico,

have you tested the different versions against speed? In a recent attempt to calculate all primes of a given integer and writing them to a listbox will unnecessary slow down the algorithm. A better approuch is to read al permutations in an array and write them into the listbox after the loop is finished. Look at this post: Prime calculation speed - #7 by MarkusR

Alexander, in this case, I’ll be writing to a file instead of adding to a list box. However, I would be curious about the speed difference between the recursive vs iterative methods. In addition to displaying the total as a “check” - should equal the factorial of the number of elements - a timer would be interesting too. Then a progress bar :grinning: What did Jim Cary say in Mask … “Somebody stop me!”

1 Like

Ciao ragazzi, la versione iterativa dell’algoritmo è decisamente più veloce. Il tempo maggiore viene mpiegato nelle operazioni di scrittura nella listbox o su file. Sul mio pc eseguendo il programma così com’è per calcolare le permutazioni di 9 elementi (9! permutazioni ) impiega 107.948 secondi il metodo ricorsivo contro i 107.537 secondi del metodo iterativo. Se però elimino le linee di codice che scrivono nella listbox i tempi si riducono a 0.940 secondi per il metodo ricorsivo contro i 0.345 di quello iterativo.
Sempre senza scrivere nella listbox mi sono spinto a calcolare 12! permutazioni. Il metodo iterativo ha impiegato circa 68 secondi contro i 929 del metodo ricorsivo.
Saluti
++++++++++++++
Hi guys, the iterative version of the algorithm is definitely faster. The biggest time is spent in the operations of writing to the listbox or file. On my pc running the program as it is, to calculate the permutations of 9 elements (9! permutations) it takes 107.948 seconds the recursive method against 107.537 seconds of the iterative method. But if I eliminate the lines of code that write in the listbox the time is reduced to 0.940 seconds for the recursive method against 0.345 for the iterative one.
Always without writing in the listbox I went to calculate 12! permutations. The iterative method took about 68 seconds against 929 for the recursive method.
Greetings

TempoVers2