Your question, your audience. Choose who sees your identity—and your question—with question security.

I need an algorithm that will generate, in lexicographic order, permutations of 'k' letters from 'n' objects.

e.g. 6 letters from an alphabet of 26

abcdef

abcdeg

abcdeh

.

abcdez

abcdfe

.

abcdze

etc.

Does anyone have access to a source?

e.g. 6 letters from an alphabet of 26

abcdef

abcdeg

abcdeh

.

abcdez

abcdfe

.

abcdze

etc.

Does anyone have access to a source?

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Given a routine for k=1, can you write a routine for k=2?

or

Given a permutation, can you find the lexicographically next permutation?

(I'm no student, Nietod, I'm 47 years old! (sometimes going on 15)) I'm trying to write a hill-climbing solution to a cipher problem and I would like to rapidly work through 6, 7, or 8 letter permutations as quickly as possible. It's easy to write a long-winded routine:

for(a=1;a<=26;a++){

for(b=1;b<=26.... etc and reject combinations with duplicated letters. I wanted something more efficient..

This sequence:

BOOL NextPerm(char *OutPut)

{

int i, j, r, s, temp;

i = 1; OutPut[c+1] = 0;

for (i=1; i <= c; i++){ OutPut[i-1] = char(n[i]+'A'-1);

/*

if(n[i] < 9) OutPut[i-1] = char(n[i]+'A');

else OutPut[i-1] = char(n[i]+'B');

*/

}

i = c-1; while (n[i] > n[i+1]) i--;

j = c; while (n[i] > n[j]) j--;

temp = n[i];

n[i] = n[j];

n[j] = temp;

if(i==0) return false;

else{

r = c;

s = i+1;

while(r > s){

temp = n[r];

n[r] = n[s];

n[s] = temp;

r--; s++;

}

return true;

}

}

....is excellent for perms of n letters from n, but I can't adapt this for r from n.

To Ozo:

No, no, yes.

To MDarling:

Yes - how does that help?

The comment of MDarling is very nice. Just add 1 to a number in 26-base, and check for equal digits. I would go for this one!!

Btw. I dont understand why u dont implement this so-called long-winded routine with for-statements. Makes your live a lot easier. And what about effiency??? You mean your algorithm is quicker or less typing?

I thought this was a homework question.

Let me guess - Singh the Code Book?

If so - have you joined the CypherChallenge list?

If not you should - lots of good hillclimbing hints in there.

why base 26 - cos letters are base 26.

a=0, b=1, ... z=25;

start at 0:

number=0;

rightmost letter = (number%26)+'A'

number=number/26;

next letter = (number % 26)+'A'

number=number/26;

next letter = (number % 26)+'A'

etc... would give AAAAAA

1 would give AAAAAB etc...

do this in a loop and your away...

BTW What you trying to solve with Hillclimbing? Playfair? ADFGVX?

regards,

Mike.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialThe elements are from 0 to (n-1)

The permatutation is of length r.

The base of the number is n.

perm[0]=0 ... perm[r-1]=0

perm[r]=0 (carry)

NextPerm()

do

add = not Inc() check for carry

if (add)

found = NoEqualDigits()

while (add && !found)

Inc

perm[0]++

while (perm[i] > n-1 && i < r)

perm[i] -= n

perm[i+1]++

return perm[r-1] > 0

The rest is open for you to fill in. If you closely look into my result you will notice the internally in the perm-class the n-based-number-class is used with all its methods.

decrypting with each one in turn as

that could take a lot (a lot!) of time.

Im writing a Playfair hillclimber.

The way I'm approaching this is to generate an n number of random squares

and decrypt with each square.

Im using a trigraph frequency table

to score each decryption. If they

meet a minimum standard then they live to the next generation. Otherwse they

die and are replaced with other random squares.

The ones that passed the scoring test

get perturbed a little by some random

swapping. Then we begin again hopefully

getting higher scores each generation.

regards,

Mike.

Yes, I admit it, #6 of Mr Singh's problems has my attention at the moment. I tried your approach of random squares and keeping the promising ones (I put limits on the frequencies of the rare, medium, and high letters (in English - ?)) to manipulate further. The trouble was, they seemed to reach a limit very quickly. ie they seemed to be blind-alleys. Maybe I'll revisit it.

The seven-letter permutations as the keyword took about 36hrs to run using Delphi Pascal. I sort of figured that with a better algorithm in C++, I could squeeze an 8-letter perm into a week(?!). (Just shows how crazy one gets trying to solve these things).

Tony

I can tell you i solved stage 6 using the playfair.exe which can be found at the cypher challenge files section.

It's quite good once you get past the clunky old fashioned UI. Start putting

common letter combinations into it

and see if what results looks like it

could be good text.

Don't get bogged down looking for

monogram frequencies or even digraph frequencies.

The best way to score this problem

is to use trigraph frequency tables

(so I'm told by successful hillclimber writers).

You can get etext versions of many books online. You can use these to

generate trigraph frequency tables.

Put them in a binary tree with their

frequency counts and you've got a good

dictionary for trigraph frequencies.

here's a link to bram stoker's dracula in etext form...

http://sailor.gutenberg.org/by-title/xx444.html

if you need any further assistance or

wish to swap ideas/code you can email

me at mdarling@zoom.co.uk.

regards,

Mike.

C++

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

Do you have specific questions?

Do you have any work on this (incomplete even) that we can review?