?

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
Not quite

I'll email you the code.