?

Log in

No account? Create an account
Grizzly Weinstein
sea_gaagii
.:.::.. .:.:.::.:

April 2009
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30

Grizzly Weinstein [userpic]
For Elfric

Simple algorithm for printing permutations without duplicates for elfric
Algorithm Question

Permute(list)
0) If list is empty return
1) Create a new set which is the old list without duplicates
2) Cycle through the new set, using each item in new set as a lead character
3) Create a new list which is the original list minus the lead character
4) Permute(new list)


#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>

namespace
{
   typedef std::vector<char> CharVector;
   typedef std::set<char> CharSet;

   int count_ = 0;
}


void Permute(CharVector itemList, int iterLength, CharVector previousItems)
{
   if (iterLength == 0)
   {
      ++count_;
      previousItems.push_back('\0');
      printf("%5d) %s\n", count_, &previousItems[0]);
      return;
   }

   // Construct a set from the vector (removes duplicates)
   CharSet iterSet(itemList.begin(), itemList.end());
   
   // Iterate through each item in the set
   for (CharSet::iterator nextSetChar = iterSet.begin();
        nextSetChar != iterSet.end();
        ++nextSetChar)
   {
      previousItems.push_back(*nextSetChar);

      // nextItemList = itemList - nextSetChar;
      CharVector nextItemList = itemList;
      nextItemList.erase(std::find(nextItemList.begin(), nextItemList.end(), *nextSetChar));

      Permute(nextItemList, iterLength-1, previousItems);
      previousItems.pop_back();
   }
}

int main(void)
{
   char items[] = { 'a', 'b', 'a', 'd' };
   CharVector itemList(items, items+4);
   CharVector previousItems;

   Permute(itemList, 4, previousItems);

   return 0;
}



There are many ways this could be made more efficient even with recursion. The goal was just to show how the algorithm worked.

Comments
Better setup of the string/vector

std::string word("AGAPE");
CharVector itemList(word.begin(), word.end());
CharVector previousItems;

Permute(itemList, itemList.size(), previousItems);
-- Note: You can send a smaller size if you want fewer letters in the r-permutation.

Don't forget this is a factorial, words like PARALLELOGRAM will easily cause overflow of the count (the recursion isn't that deep so the stack should be fine).


1) All your <'s and >'s aren't showing up, thus making the code a bit cryptic anytime you use templates =) (damn HTML formatting, anyway)

2) Duplicates letters are actually necessary for what I'm trying do. I don't want to eliminate duplicate letters. I DO want to eliminate duplicate permutations, however. So for example, in a set of (a,a,b), I would want size-2 permutations of aa, ab, and ba.

3) Algorithms for generating simple permutations of P(n,r) where r=n are abundant and easy to find. Looking at your code, that seems to be what you're doing here, too (unless I'm badly misunderstanding the code, which is a possibility). What I need is an algorithm to find the permutations of a set of size n in size-r chunks where r <= n.

Duplicate letters and chunks

1) What browser are you using? I convered to

< and >
, shows up just fine on mine.

2) It doesn't remove duplicate letters it just assures that the same letter won't show up in the same place during the same iteration (causes no duplicate words).

3) If you change the size sent to the initial Permute call to r it should work fine.

Re: Duplicate letters and chunks

Tried to get & l t and & g t to show up, didn't work :-)

Re: Duplicate letters and chunks

1) huh. Now they show up. Weird. I'm using IE (whatever is latest and greatest version)

2) ok, good

3) I got the code in email, I'll do some experimentation on it to see if it solves my problem. Appreciate the detailed response, btw =)

Actually, looking at the code more, what this LOOKS like it will do is create a subset of permutations of size 2-N.

So, if you had a set of ( a, b, c, d ), you would get as output

all permutations of a,b,c,d
all permutations of a,b,c
all permutations of a,b

But no permutations of a,d or a,c or any permutations of sets that aren't "next" to each other in the original set. Since STL sets insert things in sorted order, this does allow some prediction of results, but still, it doesn't seem to get all the permutations needed.

Or again, maybe I'm misunderstanding the code =)

Not quite

I'll email you the code.

OK, I'm grokking the code now. Pretty clever!

Now my brain is working at converting this to recursionless code. I'll bet there's a way to do that with while loops and counters.

Thanks for your help!

Better algorithm

Bettttter