Find all permutation of length N using 2 values

Question

I have set of values eg: {1,2} , {1,2,3} ... etc.

How to find all permutation including duplicates values for length N.

Input: value = {1,2} ; N =3

output: 111,112,121,122,211,212,221,222

N>no. of values

so if we take {1,2,3} then N > 3

Not able to figure out proper algorithm for this.

I thought of implementing backtracking but I don't think any modification on it can solve this problem, Please correct me if I'm wrong.

I found a C++ solution to this. All permutations of length k from n characters with repetition in CPP

Tried to convert it to C:

void print_str(char str[], char *prefix, int n, int length)
{
        if (length == 1)
        {
            for (int j = 0; j < n; j++)
                printf("%s%c\n",prefix,str[j]);
        }
        else
        {
            for (int i = 0; i < n; i++)
                {
                    char a = str[i];
                    char *b = &a;
                    print_str(str, b, n, length - 1);
                }
        }
}

int main()
{
    int length = 3;
    char *ab=malloc(sizeof(char)*length);
    char str[] = "12";
    int n = 2;
    print_str(str, ab, n, length);  
    return 0;
}

But still not getting proper output.

Output: 11 12 21 22 11 12 21 22

Note: Other Input values {A,B} {+,-} etc.

Answer 1

Why will backtracking not work? Here's an easy Python implementation:

def generate(position, result, N, values):
    if position == N:
        print(''.join(result))
        return
    for val in values:
        result[position] = val
        generate(position+1, result, N, values)

and this run with

values = ['1', '2', '3']
N = 3
result = [None]*N
generate(0, result, N, values)

Answer 2

The constraint that N should be larger than the number of values does not really matter for the algorithm.

Suppose that the set of values is {0,1,2,3,4,5,6,7,8,9} and N=3. Then the output would be all integers from 000 to 999 so we can generate them by counting from 000 to 999 one by one.

Generalizing this idea, an algorithm could start with the sequence of N copies of the first values and then "count up" until reaching N copies of the last values.

At each iteration, print the current sequence and then "count up" as when manually adding 1 to an integer: start at the first position, if the value is not the last value, change it to the next value and stop this step. If the value is the last value, set it to the first value and repeat at the next position.

If the position reaches N, then all combinations have been printed and the algorithm is done.

With {1,2} and N = 3, the sequences would be:

111  <-- initial sequence
211  <-- first position advanced
121  <-- first position reset and second position advanced
221
112
212
122
222  <-- N'th position reached with all values at the last: DONE

Note: Since I assume this is homework, I am deliberately not posting the implementation.

Update (code posted in question): the referred C++ code probably works. The translation fails to generate the correct "prefix". In any case, I would not recommend this approach in the first place since the number of recursive calls/intermediate strings can grow very large. The approach of generating combinations one by one as described above scales much better.

Answer 3

Here's another implementation using C.

The logic goes like this. Let's say for example, we have

Input: value = {1,2} ; N =3

Now, to make the first permutation _ _ _, we have a choice to take 1 or not take 1 at first position. Similarly, we have choices for all the rest positions in the same manner.

#include <iostream>
#include <vector>
using namespace std;

void recur(vector<int> &value, int n, int i, string cur, vector<string> &ans) {
  if (i == n){
    ans.push_back(cur);
    return;
  }

  for(int j = 0; j<value.size();j++){
    recur(value, n, i+1, cur+to_string(value[j]), ans);
  }
}

int main() {
  vector<int> value{1, 2};
  int n = 3;

  vector<string> ans;

  recur(value, n, 0, "", ans);

  for(int i = 0; i<ans.size();i++)
    cout<<ans[i]<<endl;

  return 0;
}

Equivalent C code

#include <stdio.h>

void recur(int value[], int s, int n, int i, char cur[]) {
  if (i == n){
    printf("%s\n", cur);
    return;
  }

  for(int j = 0;j<s;j++){
    cur[i] = value[j]+'0';
    recur(value, s, n, i+1, cur);
  }
}

int main() {
  int value[] = {1, 2};
  int s = sizeof(value)/sizeof(value[0]);
  int n = 3;
  char cur[n+1];
  cur[n] = '\0';

  recur(value, s, n, 0, cur);
  return 0;
}