Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

String permutations

in General Posts: 1,220

I know this is a textbook problem — I’m just unhappy with what I’ve found of textbook answers.

Given a string, I’d like to return all the unique permutations. However, examples that I’ve found often produce duplicate strings, or repeat the use of letters. That’s an issue when dealing with a problem that already requires recursion to avoid massive iteration.

So, for example, given the string “abc”, I’d like to get back abc, acb, bac, bca, cab, cba. But not aaa or aab, etc.

Surely there’s a nice clean implementation that’s eluded my googling. Thanks.

Tagged:

Comments

  • Posts: 707
    What do you want returned for an input of aab? 3 permutations (aab aba baa) or 6 (aAb Aab abA Aba baA bAa)
  • Posts: 1,220

    The six set. Really, a character array permutation is a clearer statement.

  • dave1707dave1707 Mod
    edited June 6 Posts: 6,828

    @Mark Here’s a version.

    function setup()
        str="abc"
        combination(str,1)
    end
    
    function combination(t,v)
        if v==#t then
            print(str)
            return
        end
        for i=v,#t do
            swap(v,i)      
            combination(t,v+1)
            swap(v,i)
        end
    end
    
    function swap(x,y)
        tab={}
        for z=1,#str do
            table.insert(tab,string.sub(str,z,z))        
        end
        tab[x],tab[y]=tab[y],tab[x]
        str=table.concat(tab)
    end
    
  • Posts: 707
    What @dave1707 said
  • dave1707dave1707 Mod
    edited June 6 Posts: 6,828

    Here’s a better version to list the permutations for larger string values.

    EDIT: I did the string abcdefghij and it showed 3,628,800 permutations. I didn’t scroll thru them to verify all were correct, I’ll leave that to someone else if they want to.
    If I did the string abcdefghijklmnopqrstuvwxyz, there would be 403,291,461,126,605,635,584,000,000 permutations.

    function setup()
        str="abcdef"
        perm={}
        combination(str,1)
        st=1
    end
    
    function combination(t,v)
        if v==#t then
            table.insert(perm,str)
            return
        end
        for i=v,#t do
            swap(v,i)      
            combination(t,v+1)
            swap(v,i)
        end
    end
    
    function swap(x,y)
        tab={}
        for z=1,#str do
            table.insert(tab,string.sub(str,z,z))        
        end
        tab[x],tab[y]=tab[y],tab[x]
        str=table.concat(tab)
    end
    
    function draw()
        background(0)
        fill(255)
        text("Slide finger to scroll list",200,HEIGHT/2)
        text("Permutations "..#perm,200,HEIGHT/2+50)
        en=math.min(st+HEIGHT//20,#perm)
        for z=st,en do
            text(perm[z],WIDTH/2,HEIGHT-(z-st+1)*20)        
        end
    end
    
    function touched(t)
        st=(st+t.deltaY)//1
        if st>#perm-10 then
            st=#perm-10
        end
        if st<1 then
            st=1
        end
    end
    
  • Posts: 1,220

    Thanks, Dave. I dragged the old 178K word dictionary out of ScramWords and am spinning the results of your routine past it to find words-within-words. I was pretty happy with how that old program used the r,g,b channels to snug all those words into. 768x768 image. Now I’m wishing I’d used the a channel to encode grade level. Some of the words popping out are pretty obscure.

  • Posts: 402

    This is another good one for coroutines:

    function permgen (a, n)
       if n == 0 then
          coroutine.yield(a)
       else
          for i=1,n do
    
         -- put i-th element as the last one
         a[n], a[i] = a[i], a[n]
    
         -- generate all permutations of the other elements
         permgen(a, n - 1)
    
         -- restore i-th element
         a[n], a[i] = a[i], a[n]
    
          end
       end
    end
    
    function perm (a)
       local n = table.getn(a)
       return coroutine.wrap(function () permgen(a, n) end)
    end
    
    str = "abcdef"
    tbl = {}
    while str ~= "" do
       table.insert(tbl,str:sub(1,1))
       str = str:sub(2)
    end
    for p in perm(tbl) do
       print(table.concat(p," "))
    end
    
  • dave1707dave1707 Mod
    Posts: 6,828

    I looked up the ScramWords link and saw a post of mine there about a 1025x1025 pixel image that I created that holds 300,249 words.

  • Posts: 1,220

    The Scramwords dictionary is a pretty close match for the Scrabble dictionary, though I compiled it from unofficial sources. Scrabble has 187K words, Scramwords 178k. A big part of that difference comes from two additional lists added to Scrabble since I made the original image.

    But honestly, I’m still just pleased that it worked out. Certainly a lot simpler toting around a modest image than a dictionary of strings.

  • dave1707dave1707 Mod
    Posts: 6,828

    @Mark Is this to play scrabble. If so, then you have to add values to the letters so you can find the words that create the most points.

Sign In or Register to comment.