?
Solved

r-permutation

Posted on 2000-02-07
12
Medium Priority
?
1,048 Views
Last Modified: 2010-05-18
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?
0
Comment
Question by:TonyNJones
  • 4
  • 3
  • 2
  • +3
12 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 2497933
We cannot provide answers to school assignments.  That is grounds for removal from this site.  (for both you and the experts involved.)  We can provide only limitied help in accademic assignments.    We can answer specific (direct) questions, like you might ask your teacher.  We can review your work and post suggestions, again, like your teacher might do.

Do you have specific questions?
Do you have any work on this (incomplete even) that we can review?
0
 
LVL 85

Expert Comment

by:ozo
ID: 2498043
Can you write a routine for k=1?
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?
0
 
LVL 3

Expert Comment

by:MDarling
ID: 2499413
can you count in base 26?
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
LVL 3

Expert Comment

by:Try
ID: 2499611
Let 'k = 2' and 'n = 4'.  Start off from there and then expand as you go along.
0
 

Author Comment

by:TonyNJones
ID: 2500109
To Nietod:
(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?
0
 
LVL 1

Expert Comment

by:aperdon
ID: 2500176
The above algorithm does not work coz it is based on swapping.

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?
0
 
LVL 3

Accepted Solution

by:
MDarling earned 600 total points
ID: 2500284
Hi Tony, sorry about my hint there
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.
0
 
LVL 1

Expert Comment

by:aperdon
ID: 2500360
I dont understand your answer....

The 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.
0
 
LVL 3

Expert Comment

by:MDarling
ID: 2500589
BTW - I hope your not thinking of running through 8! combinations and
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.

0
 

Author Comment

by:TonyNJones
ID: 2501547
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
0
 
LVL 3

Expert Comment

by:MDarling
ID: 2503298
If you haven't solved stage 6 yet than
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.


0
 

Author Comment

by:TonyNJones
ID: 2505264
Thanks for the ideas. I'll let you know...
0

Featured Post

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

601 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question