🔒 Locked

Calculating permutations

Started by Ajare Jan 11, 2005 at 4:03 PM 13 replies 1.9k views

Original Post

Jan 11, 2005 at 4:03 PM

Let's say I've an array, 1024 elements long. For simplicity's sake I'll use C. unsigned char array[1024]; Now, I want to generate all possible permutations of the data in this array. Yes, there are rather a lot - 256^1024, right, or is it 1024^256?. I can't think of any way to do this without having a for loop nested 1024 deep. Anyone know how to do this? Would it be easier in a different language?

blizzard999

Jan 11, 2005 at 4:32 PM

This is not possible!!!

The number of permutations is

1024 * 1023 * 1022 * ... * 2 * 1 = 1024!
if win calculator is right the number is near to 5,4 * exp2639

You cannot process a number of permutation like this!!! It will never exist a computer able to do that!!!

Zipster

Jan 11, 2005 at 4:54 PM

This is possible to do iteratively (check out std::next_permutation and std::prev_permutation), however at any given time you won't be able to store all the permutations at once. At any rate, 1024! is an astronomically large number, and even if you were to iterate over the set of all permutations and perform some operation on them it would take an extremely long time. I mean, an extremely long time.

Just what is it you need to do?

Extrarius

Jan 11, 2005 at 5:37 PM

To address the possible permutations of 1024 bytes, you'd need 8192 address bits (ie each pointer would need to be 1024 bytes long, and that is only to select the correct permutation! You'd need another 10 bits to select a specific element of that permutation.)
For reference: I think the most any computer uses right now is 64 address bits.

Even if you don't want to store them, that is a _LOT_ of time steps. Even if each one only takes a single cycle to generate (extremely unrealistic unless you're designing custom hardware that is insanely parallelized), it'd take until AFTER the end of time to generate them all on a 1THz machine.

Now, if you have a specific 1024 bytes you want to get the permutations for, that is 1024!, which would take ~8778 address bits, which is still more than the 64 available (and those are only available on 64 bit machines).

[Edited by - Extrarius on January 11, 2005 5:37:20 PM]

DrZoidberg

Jan 11, 2005 at 8:34 PM

do you mean 1024 permute 1024?
now nPr = n!/(n-r)!
so 1024 P 1024 = 1024!/(1024 - 1024)!
= 1024! / 0!
= 1024!

i don't see why you can't do this since the win calc is able to do 1024 factorial.

i must be missing something here.

Zipster

Jan 11, 2005 at 10:23 PM

To expand on what Extrarius said, modern computers simply don't have the addressability to handle that much data at once. Address space isn't a problem, since you can always tie together as many physical memories as you need with a virtual address space, but if your pointers can't point to the whole range of data, then that wouldn't work to begin with.

prh99

Jan 11, 2005 at 10:40 PM

Quote:
Original post by Ajare
Let's say I've an array, 1024 elements long. For simplicity's sake I'll use C.

unsigned char array[1024];

Now, I want to generate all possible permutations of the data in this array. Yes, there are rather a lot - 256^1024, right, or is it 1024^256?. I can't think of any way to do this without having a for loop nested 1024 deep. Anyone know how to do this? Would it be easier in a different language?

If you want to calculate the number of possibilities your going to need library for dealing with abitrary length integers like GMP[http://www.swox.com/gmp/]. As other have pointed out there isn't a data type long enough to hold the result. Actually finding all posibilities is impossible it would take several thousands of years and there isn't enough storage to hold all the results. In fact there are so many combinations that if you could store one gigabyte of information on a drive weighing one gram, then a list of those combinations would weight so much that it would exceed the Chandrasekhar limit (by quite a bit) and collapse into a black hole.

64-bit (or 8 bytes) would be 2 to the 64th power which is 18,446,744,073,709,551,616 you can see 256^1024 is going to be astronomical, something on the order of 1.09074813561941592946298424473e+2466. 1024 P 1024 is roughly 5.41852879605885728307692194468e+2639

[Edited by - prh99 on January 11, 2005 11:40:41 PM]

prh99

Jan 11, 2005 at 11:19 PM

Quote:
Original post by Ajare
Let's say I've an array, 1024 elements long. For simplicity's sake I'll use C.

unsigned char array[1024];

Now, I want to generate all possible permutations of the data in this array. Yes, there are rather a lot - 256^1024, right, or is it 1024^256?. I can't think of any way to do this without having a for loop nested 1024 deep. Anyone know how to do this? Would it be easier in a different language?

I used GMP (linked to in my previous post) to calculate 256^1024 exactly:

1090748135619415929462984244733782862448264161996232692431832786189721331849119295216264234525201987223957291796157025273109870820177184063610979765077554799078906298842192989538609825228048205159696851613591638196771886542609324560121290553901886301017900252535799917200010079600026535836800905297805880952350501630195475653911005312364560014847426035293551245843928918752768696279344088055617515694349945406677825140814900616105920256438504578013326493565836047242407382442812245131517757519164899226365743722432277368075027627883045206501792761700945699168497257879683851737049996900961120515655050115561271491492515342105748966629547032786321505730828430221664970324396138635251626409516168005427623435996308921691446181187406395310665404885739434832877428167407495370993511868756359970390117021823616749458620969857006263612082706715408157066575137281027022310927564910276759160520878304632411049364568754920967322982459184763427383790272448438018526977764941072715611580434690827459339991961414242741410599117426060556483763756314527611362658628383368621157993638020878537675545336789915694234433955666315070087213535470255670312004130725495834508357439653828936077080978550578912967907352780054935621561090795845172954115972927479877527738560008204118558930004777748727761853813510493840581861598652211605960308356405941821189714037868726219481498727603653616298856174822413033485438785324024751419417183012281078209729303537372804574372095228703622776363945290869806258422355148507571039619387449629866808188769662815778153079393179093143648340761738581819563002994422790754955061288818308430079648693232179158765918035565216157115402992120276155607873107937477466841528362987708699450152031231862594203085693838944657061346236704234026821102958954951197087076546186622796294536451620756509351018906023773821539532776208676978589731966330308893304665169436185078350641568336944530051437491311298834367265238595404904273455928723949525227184617404367854754610474377019768025576605881038077270707717942221977090385438585844095492116099852538903974655703943973086090930596963360767529964938414598185705963754561497355827813623833288906309004288017321424808663962671333528009232758350873059614118723781422101460198615747386855096896089189180441339558524822867541113212638793675567650340362970031930023397828465318547238244232028015189689660418822976000815437610652254270163595650875433851147123214227266605403581781469090806576468950587661997186505665475715792896

1024! isn't much better, in fact it's longer.

541852879605885728307692194468385473800155396353801344448287027068321061207337660373314098413621458671907918845708980753931994165770187368260454133333721939108367528012764993769768292516937891165755680659663747947314518404886677672556125188694335251213677274521963430770133713205796248433128870088436171654690237518390452944732277808402932158722061853806162806063925435310822186848239287130261690914211362251144684713888587881629252104046295315949943900357882410243934315037444113890806181406210863953275235375885018598451582229599654558541242789130902486944298610923153307579131675745146436304024890820442907734561827369030502252796926553072967370990758747793127635104702469889667961462133026237158973227857814631807156427767644064591085076564783456324457736853810336981776080498707767046394272605341416779125697733374568037475186676265961665615884681450263337042522664141862157046825684773360944326737493676674915098953768112945831626643856479027816385730291542667725665642276826058264393884514911976419675509290208592713156362983290989441052732125187249527501314071676405516936190781821236701912295767363117054126589929916482008515781751955466910902838729232224509906388638147771255227782631322385756948819393658889908993670874516860653098411020299853816281564334981847105777839534742531499622103488807584513705769839763993103929665046046121166651345131149513657400869056334867859885025601787284982567787314407216524272262997319791568603629406624740101482697559533155736658800562921274680657285201570401940692285557800611429055755324549794008939849146812639860750085263298820224719585505344773711590656682821041417265040658600683844945104354998812886801316551551714673388323340851763819713591312372548673734783537316341517369387565212899726597964903241208727348690699802996369265070088758384854547542272771024255049902319275830918157448205196421072837204937293516175341957775422453152442280391372407717891661203061040255830055033886790052116025408740454620938384367637886658769912790922323717371343176067483352513629123362885893627132294183565884010418727869354439077085278288558308427090461075019007184933139915558212752392329879780649639075333845719173822840501869570463626600235265587502335595489311637509380219119860471335771652403999403296360245577257963673286654348957325740999710567131623272345766761937651408103999193633908286420510098577454524068106897392493138287362226257920000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

blizzard999

Jan 12, 2005 at 4:32 AM

More and more than the number of particles in the universe!!!

Kitt3n

Jan 12, 2005 at 4:39 AM

It's part of the stl =>

std::vector numbers;
std::sort(numbers.begin(), numbers.end()); // HAS to be sorted!

// und alle permutations ausprobieren (brute force)
while (std::next_permutation(refVec.begin(), refVec.end())
{ // blah
}

// here vector is inverse-sorted

Regards

Ajare

Jan 12, 2005 at 7:04 AM

Sorry, should have been clearer. I am well aware this is completely infeasible.
Ok, so theoretically, what code would calculate this, say printing out each perm once it's been calculated? I'm just curious, that's all.

Zipster

Jan 12, 2005 at 9:31 AM

Study the logic behind std::next_permutation to see how is calculates the lexicographically next greater permutation. Otherwise I can't really think of any standard method for calculating all the permutations of a set. I assume any iterative process with the property that the next generated set is unique from all previously generated sets, while still being a permutation of the original set. It might help a little to study symmetry as it relates to permuations.

[Edited by - Zipster on January 12, 2005 1:31:37 PM]

Sharlin

Jan 12, 2005 at 2:49 PM

A little voice in my head screamed "recursion!" and indeed this seems like a textbook example on how to recursively simplify problems. So I came up with this (obviously hugely space-inefficient compared to the iterative solution which only requires constant additional storage):

#include <string>#include <iostream>// The idea is to "grow" permutations by pushing each character of // t into h in turn and recursively permuting the rest of t// (ok, bad explanation but hopefully the code is clearer :)//// t: the string to be permuted// h: the permutation being grownvoid permutations(std::string t, std::string h = ""){  if(t.empty())  {     std::cout << h << '\n';  }  else  {    for(size_t i = 0; i < t.size(); ++i)    {      permutations(t.substr(0,i) + t.substr(i+1), h + t);    }  }}// example: permutations("abcd");

Sartak

Jan 12, 2005 at 3:01 PM

As a response to Kitt3n's post, the permutation does not always have to be sorted at the beginning of the loop. If you can store a copy of the original permutation, you can permute until your permutation matches that of the original copy.

This assumes that the implementation changes the permutation to its nondecreasing order (lexicographically smallest, like 1 2 3 4 5) when fed the nonincreasing order (lexicographically largest, like 5 4 3 2 1). MOST C++ STL implementations work this way but IIRC it is not necessarily part of the standard. (This is why knowledge of your environment can be very helpful!)

#include <vector>#include <algorithm>using namespace std;int main(){  vector<int> numbers;  vector<int> original;  numbers = some_function_to_generate_numbers();  original = numbers;  do  {    next_permutation(numbers.begin(), numbers.end());  } while (numbers != original);  return 0;}

edit: cleaned some stuff up.

Zipster

Jan 12, 2005 at 3:59 PM

Recursion works, although for obvious reason shouldn't be applied in practice [smile]

Topic Locked

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