Check if two strings are permutations in C

Question

Im actually trying to make some program who can check if two strings are permutation from each other. I explain :

If I consider :

Eagle

and

Hdjoh

(I used these two examples in a previous question).

I get a permutation, and the permutation parameter is 3. Why ? Because in the alphabet : E + 3 = H, a + 3 = d etc..

I used unsigned char because if I get a z in one of my strings, I want that (for example) z + 3 = c.

What I started to do :

#include <stdio.h>
#define N 20

int my_strlen(unsigned char *string){
    int length;
    for (length = 0; *string != '\0'; string++){
        length++;
    }
    return(length);
}

int main()
{
    unsigned char string1[N], string2[N];
    int test=0, i=0, length1, length2;
    scanf("%s", string1);
    scanf("%s", string2);

    length1=my_strlen(string1);
    length2=my_strlen(string2);

    if(length1==length2){
        for(i=0; i<length1; i++){
            if(string1[i]==string2[i]){
                test=1;
                }
                else{
                    test=0;
                }
        }
        printf("Test = %d", test);
    }
    else{
        printf("Error");
    }

    return 0;
}

I just started to think about it.. So for the moment I just try to compare the two strings letter by letter.

The problem here : If i try to compare Hello and hello, or Hello and Helqo I get Test = 1.

So someone can tell me whats wrong here ?

Thanks a lot.

EDIT 1 :

#include <stdio.h>
#define N 20

int my_strlen(unsigned char *string){
    int length;
    for (length = 0; *string != '\0'; string++){
        length++;
    }
    return(length);
}

int main()
{
    unsigned char string1[N], string2[N];
    int test=0, i=0, length1, length2;
    scanf("%s", string1);
    scanf("%s", string2);

    length1=my_strlen(string1);
    length2=my_strlen(string2);

    if(length1==length2){
        for(i=0; i<length1; i++){
            if(string1[i]==string2[i]){
                test=1;
                }
                else{
                    test=0;
                    break;
                }
        }
        printf("Test = %d", test);
    }
    else{
        printf("Error");
    }

    return 0;
}

Now it's correct. I will continue.

EDIT 2 - 6.7.14 :

I am actually working and the "second part" of the program. I am looking for the d and I verify if its a permutation or not. No so easy so I need some advices, do I have to write an other function to do this ? Or just working on this part of my code :

if(length1==length2){
            for(i=0; i<length1; i++){
                if(string1[i]==string2[i]){
                    test=1;
                    }
                    else{
                        test=0;
                        break;
                    }
            }
            printf("Test = %d", test);
        }
        else{
            printf("Error");
        }

        return 0;
    }

I wrote it like this for the moment :

if(length1==length2){
        for(i=0; i<length1; i++){
                for(d=0; d<255; d++){
                    if(string1[i]==string2[i] + d){
                        permutation=1;
                }
                else{
                    permutation=0;
                    break;
                }
                }
        }
        printf("\nPermutation = %d \nd = %d", permutation, d);
    }
    else{
        printf("Not a permutation");
    }

    return 0;
}

(I know that it doesn't work but I just tried..).

Thanks by advance for the help.

what about an array `int letters[26]` and count each letter then compare the arrays... that is a pretty naive and easy implementation. — Grady Player, Jun 06 '14 at 18:35
What is the *distance* between a low-case letter and upper-case form of the same letter? — PM 77-1, Jun 06 '14 at 18:35
you are overwriting the variable `test` in the loop so only last character comparison counts. Just break from the loop as soon as you find `test = 0` — Pankrates, Jun 06 '14 at 18:37
@Pankrates : of course ! Just had to add break; Thanks a lot :). I will edit my first post and continue to do the code for my program. I will update this topic if I need. — user3605367, Jun 06 '14 at 22:01
@Pankrates If you have some time, can you please take a look to my EDIT 2 ? (I am trying to continue this program..). Thanks ! — user3605367, Jun 07 '14 at 12:19
can you use external libraries? If yes then there are already [next_permutation](http://en.cppreference.com/w/cpp/algorithm/next_permutation) for you http://stackoverflow.com/questions/3184893/use-next-permutation-to-permutate-a-vector-of-classes — phuclv, Jun 07 '14 at 12:52
Hi @LưuVĩnhPhúc, no i can't use external libraries for this program :(. Its just a little part of a big project, and using external libraries is forbidden.. — user3605367, Jun 07 '14 at 12:59
Then if you need some information you can read more here http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation — phuclv, Jun 07 '14 at 13:01
Thanks, but are you sure this is what I need for my program ? Its not the same sense of the word permutation i think :S — user3605367, Jun 07 '14 at 13:03
I know this post is old, but surely you know by now that this is not a permutation, and what you are asking for is a way to find if two strings differ by a shift cipher. — rationalcoder, May 27 '17 at 07:11

score 2 · Answer 1 · answered Jun 06 '14 at 18:35

You are only printing out the results of the last character comparison.

for(i=0; i<length1; i++){
            if(string1[i]==string2[i]){
                test=1;
                }
                else{
                    test=0;
                }
}

This goes through and compares each character and changes test each time. At the end of the loop, only the last character comparison is output.

score 1 · Answer 2 · answered Jun 06 '14 at 18:35

This is because your test variable gets updated for each character in the string.

For the strings Hello and hello, or Hello and Helqo, last character is same ('o'), hence at the end of loop, test is updated to 1.

Try with Hello and Hellm, you will get test = 0.

score 1 · Accepted Answer · answered Jun 07 '14 at 18:56

You can think about the problem like this. For two strings to be a valid permutation, the character distances have to be equal for each character in the strings. So you can check the first character distance and then loop over the other characters and verify that the distance is the same. As soon as it is not equal to first character distance, you can safely conclude that it is not a permutation.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int i;
    unsigned char string1[] = "test";
    unsigned char string2[] = "vguv";

    int slength1 = 4;
    int slength2 = 4;

    int distance;
    int is_permutation = 1;

    if (slength1 != slength2) {
        is_permutation = 0;
    }

    distance = (int)string2[0] - (int)string1[0];

    for (i=1; i<slength1; ++i) {
        if ( ((int)string2[i] - (int)string1[i]) != distance ) {
            is_permutation = 0;
            break;
        }
    }

    if (is_permutation) {
        printf("%s is a permutation of %s with distance %d\n", string1, string2, distance);
    } else {
        printf("%s is not a permutation of %s\n", string1, string2);
    }

    return EXIT_SUCCESS;
}

Please note that I have used statically defined strings and stringlengths. Your original way of reading in user input is prone to undefined behaviour. You declare a string of fixed length (20 in the OP) so if a user enters a string longer than 19 the scanf will run out of bounds and invoke undefined behaviour. This is very bad and you should read up on it.

Thx for your answer. I will test it. Just a question : why did you use this : `#include `. Because for my uni. course we have to use just the basic library.. :S That s why im trying to write all the functions on my own like strlen etc.. — user3605367, Jun 07 '14 at 20:43
that include is only for the `return EXIT_SUCCESS` you can replace that with `return 0` and get ride of the include — Pankrates, Jun 07 '14 at 20:49
Ok I see, so I will test it on keep you in touch if i don't understand something. Thanks a lot for the help ! — user3605367, Jun 08 '14 at 00:21
Hi ! So, I tested the code (I tried something with scanf too..), but there is a problem for this kind of examples : `Hhjod` and `Eagle`, are permutations with parameter 3, but the program said that it's not a permutation at all. I m looking for something to fix it, if you have any idea it will help. Thanks by advance ! @Pankrates — user3605367, Jun 09 '14 at 10:42
Maybe I have to precise that permutation could be something like this too ! Not only first letter with first letter, second with second etc.. — user3605367, Jun 09 '14 at 10:43

score 0 · Answer 4 · answered Oct 21 '15 at 13:04

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char a[100], b[100];
    int size_a, size_b, i, j, flag;
    scanf("%s", &a);
    scanf("%s", &b);
    size_a = strlen(a);
    size_b = strlen(b);
    if(size_a!=size_b)                   //if size of both strings are      unequal then print and exit
    {
        printf("no");
        exit(0);
    }
    for(i=0;i<size_a;i++)               //compare every element of a with every element of b
    {
        for(j=0; j<size_b;j++)
    {
        if(a[i]==b[j])
        {
            b[j]=32;                //when elements matches add character 'space' there, of ASCII value 32
            flag++;                 //flag guards of every successful match
        }
    }
}
if(flag==size_a&&flag==size_b)
    printf("yes");
else
    printf("no");
return 0;

}

i wrote this code and works fine for me

score 0 · Answer 5 · answered Sep 13 '16 at 01:41

0

bool IsPremutation(char* s1, char* s2, int sl1, int sl2)

{

if (sl1 != sl2)
{
    return false;
}

std::set<char> charset;

for (int index = 0;  index < (sl1 + sl2); index++)
{
    int source = (index) / sl1;

    if (source == 0)
{
    charset.insert(s1[index]);
    }
    else
    {
    charset.insert(s2[source - 1]);
    }
}

return charset.size() == sl2;

}

answered Sep 13 '16 at 01:41

omjaber

1

The above code should execute in O(n log n). The basic idea is if the two strings have identical length and number of unique characters set is equal to the strings length then the two are permutation. – omjaber Sep 13 '16 at 01:42

score 0 · Answer 6 · answered May 27 '17 at 08:19

I know this is old, but the quality of answers is disturbing. First, you aren't really looking for a permutation; you are checking to see if two strings are different by a shift cipher.

A cleaner version of the accepted answer that handles case conversions like you mentioned:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>


int shifted(const char* a, const char* b, int* amount) {
    size_t len_a = strlen(a);
    size_t len_b = strlen(b);
    if (len_a != len_b) return 0;

    int shift_amount = *b - *a;
    for (; *a; a++, b++)
        if (tolower(*b) - tolower(*a) != shift_amount) return 0;

    *amount = shift_amount;
    return 1;
}

int main(void) {
    const char *a = "shift";
    const char *b = "tigU";

    int shift_amount = 0;
    if (shifted(a, b, &shift_amount))
        printf("Shifted by amount: %d\n", shift_amount);
    else
        printf("Not shifted\n");

    a = "shift";
    b = "shifT";
    if (shifted(a, b, &shift_amount))
        printf("Shifted by amount: %d\n", shift_amount);
    else
        printf("Not shifted\n");

    a = "shift";
    b = "shifv";
    if (shifted(a, b, &shift_amount))
        printf("Shifted by amount: %d\n", shift_amount);
    else
        printf("Not shifted\n");

    return EXIT_SUCCESS;
}

Output:

Shifted by amount: 1
Shifted by amount: 0
Not shifted

score 0 · Answer 7 · answered Oct 19 '17 at 23:09

#include <stdio.h>
#define possiblechars 256

int is_permutation(char *str1, char *str2)
{
    int count1[possiblechars] = {0};
    int count2[possiblechars] = {0};
    int i;

    //sets count arrays '0' for 256 times
    for (i = 0; str1[i] && str2[i]; i++)
    {
        count1[str1[i]]++;
        count2[str2[i]]++;
    }

    //interates until either string 1 or 2 hits null
    //increments individual indexes of the count arrays
    if (str1[i] || str2[i]){
        return 0;
    }

    //if different lengths, then return false
    for (i = 0; i < possiblechars; i++){
        if (count1[i] != count2[i]){
            return 0;
        }
    }
    return 1;
}

int main(int argc, char *argv[])
{
    char str1[] = "Eagle";
    char str2[] = "Hdjoh";
    if (is_permutation(str1, str2)){
      printf("Permutation\n");
    }
    else {
      printf("Not a permutation\n");
    }
    return 0;
}

Pritam Mitra · Answer 8 · 2017-10-24T14:37:52.963

#include <stdio.h>
#include <conio.h>
#include <string.h>
#define N 20

int my_strlen(unsigned char *string)
{
    int length;

    for (length = 0; *string != '\0'; string++)
    {
        length++;
    }
    return (length);
}

int main()
{
    unsigned char string1[N], string2[N];
    int permutations = 0, i = 0, d = 0, length1, length2;
    scanf("%s", string1);
    scanf("%s", string2);
    length1 = my_strlen(string1);
    length2 = my_strlen(string2);
    d = string1[0] - string2[0];   //finding out the distance
    if (length1 == length2)
    {
        for (i = 0; i < length1; i++)
        {
            if (d < 0)           //if less then 0 then String2 >String1
            {
                if (string2[i] == string1[i] + d * (-1)) //when d enters here d will be always negative
                {
                    permutations=1;
                }
                else
                {
                    permutations = 0;
                    break;
                }
            }
            else           //else String1 >String2
            {
                if (string1[i] == string2[i] + d)
                {
                    permutations = 1;
                }
                else
                {
                    permutations = 0;
                    break;
                }
            }
        }
        printf("Permutations=%d\n and distamce=%d", permutations, d);
    }
    else
    {
        printf("Error");
    }
    return 0;
}

Sure...!!! Everything is same just used a variable 'd' which holds the distance if d<0 -----> here trying to check if the the 1st string i.e string1 is greater then string2 now why is the need to check ??? since d here is the key factor to check if there permutations exists between the string so i tried to keep a check that whether the first string is greater or the second string ??? spare me if a newbie in explaining things..!!! — Pritam Mitra, Oct 24 '17 at 14:25
All code and explanation belong in your answers. Not in the comments! — Xpleria, Oct 24 '17 at 14:27

Check if two strings are permutations in C

8 Answers8