Permutation of an array of strings

Question

I am solving this challenge : https://www.hackerrank.com/challenges/permutations-of-strings/problem

I am using this algorithm : https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Suppose I enter my array of strings as {"a", "b", "c"}, then the output should be :

a b c 
a c b
b c a
c b a
b a c
c a b

Since there are 3 distinct strings, there are 3! = 6 permutations.

The program is also supposed to handle duplicate cases, so if I enter {"a", "b", "b"}, there will only be 3! / 2! = 3 permutations.

Anyways when my program reaches c b a then it quits. Why? How can I fix that?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void swap(char** s1, char** s2) // to swap two strings
{
    char* temp = *s1;
    *s1 = *s2;
    *s2 = temp;
}
int next_permutation(int n, char **s)
{
    /**
    * Complete this method
    * Return 0 when there is no next permutation and 1 otherwise
    * Modify array s to its next permutation
    */
    int k, i, l;
    k = i = l = 0;

    for(i = n - 2; i >= 0; i--) // first step
        if(strcmp(s[i], s[i + 1]) < 0) {
            k = i;
            break;
        }


    if(i == -1)
        return 0;

    for(i = n - 1; i >= k + 1; i--) // second step
        if(strcmp(s[k], s[i]) < 0) {
            l = i;
            break;
        }


    swap(&s[k], &s[l]); // third step

    for(i = k + 1; i < n / 2; i++) // fourth step
        swap(&s[i], &s[n - i - 1]);

    return 1;
}

int main() // locked code
{
    char **s;
    int n;
    scanf("%d", &n);
    s = calloc(n, sizeof(char*));
    for (int i = 0; i < n; i++)
    {
        s[i] = calloc(11, sizeof(char));
        scanf("%s", s[i]);
    }
    do
    {
        for (int i = 0; i < n; i++)
            printf("%s%c", s[i], i == n - 1 ? '\n' : ' ');
    } while (next_permutation(n, s));
    for (int i = 0; i < n; i++)
        free(s[i]);
    free(s);
    return 0;
}

Contrary to what you say, your program just outputs `a b c` then exits. This is because you break out of those loops at totally the wrong time. — ikegami, Jun 01 '20 at 05:58
On Xcode when I enter 3, a, b, c, each on a new line I get output till `c b a` then it repeats. Anyways what should I do? — Divyanshu Varma, Jun 01 '20 at 06:06
Please [edit] your questions to provide that additional information directly there, instead of hiding it down here in the comments. A good [mre] requires several pairs of relevantly different sample input along with the resulting output. — Yunnosch, Jun 01 '20 at 06:11
If that's true, then "Xcode" is broken. `strcmp(s[i], s[i + 1]) < 0` should never be true for the initial array of `a b c`, so the loop will continue until `i == n - 1`, which means you return `0`. Before doing any permutations. Who you do you think I trust more, Xcode or you? — ikegami, Jun 01 '20 at 06:14
At least it finds the correct `k` (although inefficiently) in that situation. It fails to find the correct `k` in other situations (exiting the prematurely). Similar problems exists in the second step. You somehow managed to get the third step correct, while the fourth step is a hot mess. Why not just swap pointers like in the third step?! Anyway, there's no way this program comes even close to outputting the correct result except for infinitely looping the last result. — ikegami, Jun 01 '20 at 06:21
This is a challenge from Hackerrank, as provided in the link. — Divyanshu Varma, Jun 01 '20 at 06:24
I will provide the following tips for the first step: Wouldn't it make sense to start at largest index and work backwards since you want the largest index matching a condition? That way, you could exit the loop sooner... And if you initialize `k` to a value it can't possibly end up as, then you could check if `k` still has that value to determine if the condition was ever true. — ikegami, Jun 01 '20 at 06:24
Like I said, homework. The fact that it's self-imposed doesn't matter. — ikegami, Jun 01 '20 at 06:25
`strcmp("a", "b")` return a negative value, possibly (but not necessarily) `-1` ...Sorry, I meant should *always* be true. The rest is correct; I just flipped a word. (`strcmp(s[i], s[i + 1]) < 0` will always be true for the initial array of `a b c`, so you'll never call `break`, so the loop will continue until `i == n - 1`, which means you `return 0.`) — ikegami, Jun 01 '20 at 06:42
[Print all permutation in lexicographic order](https://stackoverflow.com/questions/29928236/print-all-permutation-in-lexicographic-order)?? — David C. Rankin, Jun 01 '20 at 07:31
Yes. But I am trying to implement the algorithm on the Wikipedia link I provided. — Divyanshu Varma, Jun 01 '20 at 07:35

score 1 · Accepted Answer · answered Jun 01 '20 at 09:20

This is the final code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void swap(char** s1, char** s2) // swaps two strings
{
    char* temp = *s1;
    *s1 = *s2;
    *s2 = temp;
}
int next_permutation(int n, char **s) // function to complete
{
    int k, i, l;
    k = i = l = 0;

    for(i = n - 2; i >= 0; i--) // step 1
        if(strcmp(s[i], s[i + 1]) < 0) {
            k = i;
            break;
        }


    if(i == -1)
        return 0;

    for(i = n - 1; i >= k + 1; i--) // step 2
        if(strcmp(s[k], s[i]) < 0) {
            l = i;
            break;
        }


    swap(&s[k], &s[l]); // step 3

    int inner = k + 1 + n - 1; // step 4
    int cond = inner / 2;
    for(i = n - 1; i > cond; i--)
        swap(&s[i], &s[inner - i]);

    return 1;
}

int main() // locked code
{
    char **s;
    int n;
    scanf("%d", &n);
    s = calloc(n, sizeof(char*));
    for (int i = 0; i < n; i++)
    {
        s[i] = calloc(11, sizeof(char));
        scanf("%s", s[i]);
    }
    do
    {
        for (int i = 0; i < n; i++)
            printf("%s%c", s[i], i == n - 1 ? '\n' : ' ');
    } while (next_permutation(n, s));
    for (int i = 0; i < n; i++)
        free(s[i]);
    free(s);
    return 0;
}

Good work. [My version.](https://pastebin.com/1ynQuC72) /// I believe whole declaring at the top is bad and declerations should be limited in scope. /// `for (int i=n; i--; )` is a common idiom for looping from N-1 to 0 (for non-neg N). More importantly, note how I used `k = n` instead of `k = -1`? That's to avoid the need for neg nums. There's no reason to use signed integers for array indexes/sizes! /// There's no point in using `i` in step 2; using `l` directly will do. (In other circumstances, I'd avoid `l` cause it looks like `1`.) /// We did step 4 a little different, but both are fine. — ikegami, Jun 01 '20 at 18:08

Permutation of an array of strings

1 Answers1