?

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
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 =)