CODEWITHSUNDEEP
arraysalgorithmpermutationheaps-algorithm
amirali
amirali

Reputation: 1964

Permutation algorithm for n characters in x positions

e.g. A permutation algorithm for {&, *, %} to be placed in 8 positions:

  1. &&&&&&&&&
  2. &&&&&&&&*
  3. &&&&&&&&%
  4. &&&&&&&*%
  5. &&&&&&&**

...

Heap's permutation algorithm I saw on the Internet works just for those who the number of characters are equal to the number of positions, And those who can work with unequal number of characters and number of positions, Only work with integers, Not characters. I also have to say I haven't reached any working algorithm up to now, As I don't know anything about algorithms. I had one try, Which I couldn't name it algorithm after I saw heap's algorithm! In case it helps:

  1. Add & to the output array.
  2. Add % to the output array on a new index.
  3. Add * to the output array on a new index.
  4. Do a recursive algorithm for each three.

But I obviously can't handle array indexes. I have also tried using numbers from 0 to 2 for &, %, *; But I didn't reach a good answer.

Upvotes: 1

Views: 309

Answers (2)

RaffleBuffle
RaffleBuffle

Reputation: 5455

You can use the standard "odometer" method (IDEOne):

static void permute(String str, int len)
{    
  char[] chars = str.toCharArray();

  int[] idx = new int[len];

  char[] perm = new char[len];    
  Arrays.fill(perm, chars[0]);

  while(true)
  {      
    System.out.println(new String(perm));

    int k=idx.length-1;
    for(; k>=0; k--)
    {
      idx[k] += 1;
      if(idx[k] < chars.length) 
      {
        perm[k] = chars[idx[k]];
        break;
      }
      idx[k] = 0;
      perm[k] = chars[idx[k]];
    }
    if(k < 0) break;
  }
}

Test:

public static void main(String[] args)
{
  permute("&*%", 8);
}

Output:

&&&&&&&&
&&&&&&&*
&&&&&&&%
&&&&&&*&
&&&&&&**
&&&&&&*%
&&&&&&%&
&&&&&&%*
&&&&&&%%
&&&&&*&&
<snip>
%%%%%%**
%%%%%%*%
%%%%%%%&
%%%%%%%*
%%%%%%%%

Upvotes: 2

SargeATM
SargeATM

Reputation: 2841

The permutations can be listed out by counting base 3.

  • & = 0
  • * = 1
  • % = 2

The algorithm (pseudocode)

Start i=00000000 and end at 22222222 in base 3:
    str_i = encode i in { &, *, % } character set
    print str_i
    i = i + 1 (in base 3)

Code Example (in Python)

def main():
  start = int('00000000', 3)
  end = int('22222222', 3)
  for i in range(start, end + 1):
    # convert binary to base 3
    perm_base3 = str_base(i, 3)
    perm_charset = encode_to_charset(perm_base3)
    print(perm_charset)

# custom character set
# & = 0
# * = 1
# % = 2
def encode_to_charset(str_number_base3):
  ret = []
  for c in str_number_base3:
    if c == '0':
      ret.append('&')
    elif c == '1':
      ret.append('*')
    elif c == '2':
      ret.append('%')
    else:
      pass #TODO handle error here
  return "".join(ret)

#
# Utility functions
# https://stackoverflow.com/questions/2063425/python-elegant-inverse-function-of-intstring-base
#
def digit_to_char(digit):
    if digit < 10: return chr(ord('0') + digit)
    else: return chr(ord('a') + digit - 10)

def str_base(number,base):
    if number < 0:
        return '-' + str_base(-number,base)
    else:
        (d,m) = divmod(number,base)
        if d:
            return str_base(d,base) + digit_to_char(m)
        else:
            return digit_to_char(m)

main()

Live Example (on repl.it)

https://repl.it/@KyleMarshall1/PermutationAlgorithm

Upvotes: 2

Related Questions