Permutations in C

Question

I searched on the internet for an algorithm for permutations in C and I found the following function:

void permute(char *a, int l, int r)
{
    int i;
    if (l == r)
        printf("%s\n", a);
    else
    {
        for (i = l; i <= r; i++)
        {
            swap((a + l), (a + i));
            permute(a, l + 1, r);
            swap((a + l), (a + i)); //backtrack 
        }
    }
}

The link to the page is: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

The function looks elegant and short but quite frankly, I don't understand how it works, so I decided to implement my own understanding of the problem and came up with the following code:

#include <stdio.h>
#include <string.h>

void fn(char *str, int k, int n);

int main(void)
{
    char str[] = "abcd";
    fn(str, strlen(str), strlen(str));

    return 0;
}

void swap(char *a, char *b)
{
    char tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void fn(char *str, int k, int n)
{
    for (int i = 1; i <= k; i++)
    {
        if (i == 1)
        {
            puts(str);
        }
        else
        {
            for (int j = 1; j < i; j++)
            {
                if (i == n)
                    putchar('\n');

                swap(str + n - i, str + n - i + j);
                fn(str, i - 1, n);
                swap(str + n - i, str + n - i + j);
            }
        }
    }
}

My question is, should I be using that function or my function? Is there any advantage to that function over my function, given that my function has two loops?

Answer 1

should I be using that function or my function?
Is there any advantage to that function over my function, given that my function has two loops?

Let us look at each.

The l with it

See any problem with swap((a+1), (a+i));? That code swaps the wrong elements. Correct code, like what is posted, is swap((a+l), (a+i));. Moral of the story. Do not use an object called l. Too easy to confuse with 1. Makes review unnecessarily difficult - even when code is right.

Advantage: OP

Unneeded ()

Both below are the same. One drier than the other.

swap((a+l), (a+i));
swap(a+l, a+i);

Advantage: OP

Check the zero case

Both work well enough with "" (does not print anything), yet original code could have trouble with permute("", 0, strlen("") - 1); given strlen("") - 1 is SIZE_MAX.

The "" case deserves explicit definition. I could see f("") printing one line of nothing - after all 0! is 1.

Advantage: OP

Check the wide case

With very long strings, longer than INT_MAX, code breaks down as int is insufficient whereas size_t is best for array indexing. Yet time to print such a set of permutations is many times the age of the universe, so we will set aside this concern.

Advantage: Neither.

Not const

More useful to have a function that does not require a char *, but can work with a const char *

Advantage: Neither.

Functional difference!: Extra lines

OP's code for "abc" prints the below. Original code does not print the extraneous empty lines

abc
acb

bac
bca

cba
cab

Suggest dropping the if (i == n) putchar('\n');

Advantage: Original

Repeated test within loop

Why test for k==1 repeatedly? Perhaps

void fn(char *str, int k, int n) {
  if (k >= 1) {
    puts(str);
    for (int i = 2; i <= k; i++) {
      for (int j = 1; j < i; j++) {
        swap(str + n - i, str + n - i + j);
        fn(str, i - 1, n);
        swap(str + n - i, str + n - i + j);
      }
    }
  }
}

Advantage: Original

Function name, parameter names

Both are wanting in their declaration. fn is not an informative name for printing string permutations. What is k? How it should be called lacks guidance on correct usage.

void permute(char *a, int l, int r) {
void fn(char *str, int k, int n) {

Perhaps instead a wrapper function? Then make permute(), fn() static.

void print_str_permute(char *str) {
  int length = (int) strlen(str); 
  permute(str, 0, length - 1); 
  // or 
  fn(str, length, length);
}

Advantage: Original

Big O

I put a function counter in both approaches. OP was O(n!) and apparently so was the original. Thus OP's concern about "my function has two loops" did not worsen O().

Advantage: Neither

---

Recommend: Use the best parts of the two.

For me, I would prefer a solution that worked with a const char *.