Skip to main content
gamedev.net
🔒 Locked

Help with algorithm

Started by SoxFan44 Sep 13, 2006 at 5:52 PM 9 replies 1.2k views
Original Post
SoxFan44
SoxFan44
Hi, I'm having trouble with this. Say I have a 10 element 1 dim. array: int[] arr = {2, 9, 65, 34, 5, 8, 0, 3, 12, 6}; I need to write an algorithm that will loop and give me every possible combination of all numbers at all possible positions in the array. I'm pretty sure there are 10! possibilities, but I can't figure it out. I was thinking of doing something similiar to a bubble sort, then rotate the entire array by 1, then repeat 10 times, but want to make sure that will work. I'm sorry if this isn't clear, but thanks for any help!
Simian Man
Simian Man
Judging by the fact that you just registered here, and the nature of your question, I'd say this is homework. Homework solutions are disallowed by this site, but I'll give you a hint: Permutations!

Good Luck
Fruny
Fruny
If you have to write the algorithm (i.e. it's homework) it won't help you but in C++ I would go for:

#include <algorithm>#include <iostream>int main(){   int arr[10] = {2, 9, 65, 34, 5, 8, 0, 3, 12, 6};   std::sort(arr, arr+10);   bool running = true;   do   {      running = std::next_permutation(arr, arr+10);      for(int i=0; i<10; ++i)         std::cout << arr << ' ';      std::cout << std::endl;   } while(running);}
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
SoxFan44
SoxFan44
Quote:
Original post by Simian Man
Judging by the fact that you just registered here, and the nature of your question, I'd say this is homework. Homework solutions are disallowed by this site, but I'll give you a hint: Permutations!

Good Luck


Thanks for the response, it's most certainly *not* homework though. I graduated several years ago and am working on a side project right now. I'll do a bit of research and post again if I have any questions. Thanks again!
TheAdmiral
TheAdmiral
I hate to sound condescending or superior, but there is only one combination on ten items out of ten. Do you mean permutations? I suspect so, as there are 10! of those.

I sha'n't give you any code, either, but the solution goes just like the human thought process:

Choose the first object. There are ten ways to do this.
Given that the first object is chosen, choose the second object. There are nine ways to do this.
Given that the first two objects are chosen, choose the third. There are eight ways to do this.
...
Given that the first nine objects are chosen, choose the last object. There is only one way to do this.

10! permutations indeed. Supposing that the objects were initially stored in a std::vector, say, the permutation set would best be created recursively. I'll leave you to fill in the details.

By the by, I hope you aren't planning on listing all of these permutations, as there are upwards of three and a half million of them.

Regards
Admiral
Ring3 Circus - Diary of a programmer, journal of a hacker.
SoxFan44
SoxFan44
OK, so I get it working for a 1 dim array. Now, say I have a struct that has:

struct Person, p[10] = {{1, "test", "last"} {.......}}
int id
string firstname
string lastname

And I have an array of Person. Is there a way to get the list of permutations based in the int in my struct?

Thanks again for the help!
Nitage
Nitage
Which language are you using? In C++, use std::next_permutation like Fruny suggestd (it's slightly more complicated with structs, but not much)

struct Person{   int id;   string firstname;   string lastname;};Person p[10] = {{1, "test", "last"} {.......}};bool ordering(const Person& left, const Person& right){   return left.id < right.id;}int main(){   std::sort(p, p+(sizeof(p)/sizeof(p[0]),ordering);   bool running = true;   do   {      running = std::next_permutation(p,p+(sizeof(p)/sizeof(p[0]),ordering);      for(size_t i=0; i<(sizeof(p)/sizeof(p[0]); ++i)         std::cout << p.firstname << ' ' << p.lastname << '\n';      std::cout << std::endl;   } while(running);}

Fruny
Fruny
Use a symbolic constant for the size rather than sizeof(p)/sizeof(p[0]). (Yes, I know I used a "magic number". So sue me.)
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Nitage
Nitage
It was only an example. IMO boost::array would be the most appropriate solution instead of a symbolic constant.
Emmanuel Deloget
Emmanuel Deloget
Quote:
Original post by Anonymous Poster
Funny you didn't suggest using std::vector or similar.


std::vector can't be initialized with an initializer list. Buf of course, if the list is gradually constructed, the OP should use a std::vector. Anyway, that doesn't change the algorithms.

Regards,

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.