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?
1 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
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 *.