C++ Challenge: permutations

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 21169 Views - Last Post: 14 January 2012 - 04:33 PM

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

C++ Challenge: permutations

Post icon  Posted 14 May 2011 - 12:36 PM

Ok so the goal of this challenge is to write a function that takes a string and returns a sequence of all possible permutations.

So for example if I had the string "ab" then the sequence ["ab", "ba"] would be returned.

here is a Wikipedia link on permutations.

Here is a bigger example, If I have the string "ish" then I would have the following permutations
ish
ihs
shi
sih
his
hsi


I found this tool for generating the permutations, that way you can check it.

And for extra kudos don't use the C++ standard library for finding the permutations ;)
For those of who are less familiar with the C++ stranded library have a look at the algorithm library.

Here is a good function prototype to use, you can make it what ever you want though.
void P(std::vector<std::string>& perms, std::string str);


Also one last thing, please use spoiler tags when posting solutions. that way everyone can have a fair chance at coming up with there own solution.

[ spoiler] :code: [ /spoiler]
Spoiler


And most importantly, have fun!!

once the challenge gets going some more, ill post my two solutions. one using the standard library and the other without.

Is This A Good Question/Topic? 4
  • +

Replies To: C++ Challenge: permutations

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: C++ Challenge: permutations

Posted 14 May 2011 - 12:54 PM

Spoiler

Was This Post Helpful? 2
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: C++ Challenge: permutations

Posted 14 May 2011 - 01:00 PM

very nice!! kudos for doing it with out the standard library!!
Was This Post Helpful? 0
  • +
  • -

#4 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: C++ Challenge: permutations

Posted 14 May 2011 - 01:36 PM

ok, here's my two solutions. in my non-std one i still used std::vector and std::string but it's in the heart of what i meant.

Spoiler

Was This Post Helpful? 0
  • +
  • -

#5 RevTorA  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 76
  • View blog
  • Posts: 251
  • Joined: 22-April 11

Re: C++ Challenge: permutations

Posted 16 May 2011 - 08:48 AM

This was fun actually. I've never gotten to use this method before hehe. Not the fastest implementation however.

Spoiler


Now to check out the other solutions.

Edit: Looks like I was mostly in line with everyone else... Mine's longer though, I probably didn't think it through enough. Was fun anyway :D

Edit2: I'm also really proud of myself because my code worked perfectly the first time I ran it... Not a huge program, but still. How often does that happen to you guys? XD

Edit3: 4 1/2 minutes to calculate and print all 362880 permutations from a 9 letter word... Do I dare try 10? lol. Guess that's why recursion isn't used very often

This post has been edited by RevTorA: 16 May 2011 - 09:34 AM

Was This Post Helpful? 1
  • +
  • -

#6 sarmanu  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 966
  • View blog
  • Posts: 2,362
  • Joined: 04-December 09

Re: C++ Challenge: permutations

Posted 17 May 2011 - 04:00 AM

Spoiler


And without STL, not that much of a difference except the need of messy dynamic memory allocation:
Spoiler

This post has been edited by sarmanu: 17 May 2011 - 08:57 AM

Was This Post Helpful? 2
  • +
  • -

#7 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: C++ Challenge: permutations

Posted 17 May 2011 - 09:25 AM

i like a lot, it's non-recursive! i couldn't think of a non recursive way :(
i didn't think to generate the permutations as indexes rather than stirngs :)
Was This Post Helpful? 0
  • +
  • -

#8 RetardedGenius  Icon User is offline

  • >>──(Knee)──►
  • member icon

Reputation: 126
  • View blog
  • Posts: 555
  • Joined: 30-October 10

Re: C++ Challenge: permutations

Posted 17 May 2011 - 09:58 AM

I wrote this a few weeks ago to improve my understanding of permutations and combinatorics. I've subsequently used it solve several of the Project Euler problems.

Unfortunately my code generates all of the permutations for an array of integers, as opposed to a string; the concept however is identical, so I hope that this is OK?

Spoiler

Was This Post Helpful? 1
  • +
  • -

#9 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: C++ Challenge: permutations

Posted 17 May 2011 - 03:46 PM

nice, ive only solved 12 of the project Euler problems. i might pick that up again some time :)
Was This Post Helpful? 0
  • +
  • -

#10 RetardedGenius  Icon User is offline

  • >>──(Knee)──►
  • member icon

Reputation: 126
  • View blog
  • Posts: 555
  • Joined: 30-October 10

Re: C++ Challenge: permutations

Posted 17 May 2011 - 04:02 PM

View Postishkabible, on 17 May 2011 - 11:46 PM, said:

nice, ive only solved 12 of the project Euler problems. i might pick that up again some time :)

They're great fun, I finished my 50th today. :smartass:
As coincidence would have it I started a topic about Project Euler earlier today, here.
Was This Post Helpful? 0
  • +
  • -

#11 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: C++ Challenge: permutations

Posted 18 May 2011 - 05:49 AM

you know if you could stuff that code into a function with templates it would not just apply to arrays of integers but rather to any container whose elements support the '=' operator.

and if you used the copy constructor instead it would apply to any copyable data type.

new ((void*)&a[i]) T(x);



this explicitly calls the copy constructor without allocating new space. it has to be one of weirdest syntaxs ever but it works never the less.

This post has been edited by ishkabible: 18 May 2011 - 05:59 AM

Was This Post Helpful? 0
  • +
  • -

#12 RetardedGenius  Icon User is offline

  • >>──(Knee)──►
  • member icon

Reputation: 126
  • View blog
  • Posts: 555
  • Joined: 30-October 10

Re: C++ Challenge: permutations

Posted 18 May 2011 - 01:56 PM

That's a cool idea, I was aware that that is possible, although I am not sure that my C++ knowledge is quite ready for that. I will definitely encapsulate it into a function with templates at some point though, I will post it as snippet as well. :)
Was This Post Helpful? 0
  • +
  • -

#13 CTphpnwb  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2934
  • View blog
  • Posts: 10,135
  • Joined: 08-August 08

Re: C++ Challenge: permutations

Posted 18 May 2011 - 04:25 PM

I just saw this topic and was going to write this, but look what I found in my miscellaneous code folder:
Spoiler

Not sure when I wrote it.

Sorry about the tags. I was just about to fix it!

This post has been edited by CTphpnwb: 18 May 2011 - 04:29 PM
Reason for edit:: please use spoiler tags when posting code for a challnge

Was This Post Helpful? 0
  • +
  • -

#14 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: C++ Challenge: permutations

Posted 18 May 2011 - 04:33 PM

spoiler tags please :)
Was This Post Helpful? 0
  • +
  • -

#15 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: C++ Challenge: permutations

Posted 13 January 2012 - 02:16 AM

There is a std::next_permutation in the algorithm header, that makes the stdlib version fairly trivial.

Spoiler


Edit: wait, nm, ishkabible seems to have used it.

This post has been edited by Karel-Lodewijk: 13 January 2012 - 02:28 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2