Permutations Problem

[amberleef]

Hi i have this program i got off the net, im a beginner on this stuff so i try explain best i can :)

i think programs have a sort in place to check if array is in 1 to N order before permutation call, if i was to leave out the sort then i could put values where i want to speed things up.
e.g: say{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,30,29,28,27,26,25,24,23,22,21,20,19,18,17,
15,16}

and i had to stop the program...(restart pc or other reason)

next time i start the program i change the array to order it finished at so i dont have to go through array from the beginning?

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

//using arrays of string

void display(string* strstart, string* strend)
{
  for(string* it= strstart;it!=strend;++it)
   cout<<*it<<" ";
  cout<<endl;
}

int main()
{
  string* strarray=new string[31];
  strarray[0]="ON";
  strarray[1]="OFF";
  strarray[2]="ON";
  strarray[3]="OFF";
  strarray[4]="ON";
  strarray[5]="OFF";
  strarray[6]="ON";
  strarray[7]="OFF";
  strarray[8]="ON";
  strarray[9]="OFF";
  strarray[10]="ON";
  strarray[11]="OFF";
  strarray[12]="ON";
  strarray[13]="OFF";
  strarray[14]="ON";
  strarray[15]="OFF";
  strarray[16]="ON";
  strarray[17]="OFF";
  strarray[18]="ON";
  strarray[19]="OFF";
  strarray[20]="ON";
  strarray[21]="OFF";
  strarray[22]="ON";
  strarray[23]="OFF";
  strarray[24]="ON";
  strarray[25]="OFF";
  strarray[26]="ON";
  strarray[27]="OFF";
  strarray[28]="ON";
  strarray[29]="OFF";
  strarray[30]="ON";

display(strarray,strarray+31);

  for(int i=0; i<8.22283865417792281772556288e+33 -1; ++i)
	  
  {
    next_permutation(strarray,strarray+31);    
    display(strarray,strarray+31);
  }

  return 0;
}

Thanks :)

[mik2718]

Not sure what you are doing but I think an int will always be less than that giant number you have there

[amberleef]

LoL!!!

That giant number yes isnt that the number of permutations of 31!

The numbers in the braces are from 0-51
As the permutations grow so do change the positions of the numbers if i stopped the permutations when it got down to 14, took note of where numbers are positioned, next time opening the program i change the array to the one it finished at last time so it just carries on from where it left off, instead of having to start all over again?

[mik2718]

Right, 31! = 8.22283865417792281772556288e+33

Your problem is that an integer variable is usually 32 bits and a (signed) integer has a maximum value of 2,147,483,647
much less than 31! After it reaches the top it loops around (without an error being caused) and so
i<8.22283865417792281772556288e+33 -1 will always be true - loops forever

Even if you use a 64 bit integer that only goes up to 9,223,372,036,854,775,807 still much less than 31!

The number you have there will be represented as a double precision floating point number. The problem there - this has only a certain amount of accuracy (about 15 digits) and so adding or subtracting 1 will leave it unchanged.

To represent this number exactly you need to use bignums, you can get these from a library somewhere.

How long are you expecting this program to run?

Back with an edit.

A lot of those permutations you are generating will be indistinguishable since you only have two symbols (not 31)
You have 15 "OFF" and 16 "ON". The number of distinct sequences of these is "31 choose 15" which is much less then 31!

31 choose 15 = 300,540,195 a much more manageable number - now how to generate those sequences?

[amberleef]

"ON" and "OFF" were just examples i used you can fill with 31 different ones like names of people etc... isnt chosing (= combinations)?

[ResidentBiscuit]

Uh what are you trying to do here?

[mik2718]

well, here is a permutation of 31 different names

Pete, Bob, John, Jane, ......., Sam

and another permutation

Bob, Pete, John, Jane, ....., Sam

suppose I have this permutation of "ON" and "OFF"

ON, ON, OFF, ON, ......, ON

and this one

ON, ON, OFF, ON, ....., ON

its a different one since I swapped the first two objects - notice the difference?

No?

So there are fewer ways of arranging 15 "OFF" and 16 "ON" then there are of arranging 31 different names

For your program, how about starting off with a smaller array of different names (like 5 or something)

You could experiment with increasing the number gradually to see how many permutations you are getting

[ResidentBiscuit]

These are issues that even super computers can't solve directly. 31 names is really not that much in the real world. Imagine if you had 100,000!. Would take lifetimes to compute all that. So you should start with a smaller number like mik2718 said.

[mik2718]

Indeed,

Apparently the age of the universe is 4.336e17 seconds so if amberleef started his program at the big bang and processed 1,000,000,000
records a second continuously he would now have processed 4.336e26 records and be about a hundred millionth of the way through.

[ResidentBiscuit]

And now we see why it's a good idea to plan before you program haha :)