Skip to content

Instantly share code, notes, and snippets.

@cslarsen

cslarsen/permut.cpp

Last active September 5, 2015 07:35
Show Gist options
  • Save cslarsen/458043 to your computer and use it in GitHub Desktop.
Save cslarsen/458043 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. cslarsen revised this gist Dec 8, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion permut.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -40,7 +40,7 @@ bool zero(int counts[MAX])
    */
    bool uniq(int counts[MAX])
    {
    int x = 0;
    int x = 0;
    for ( int n=0; n<MAX; ++n )
    x ^= counts[n] ^ n;
    return x == 0;
  2. cslarsen revised this gist Dec 8, 2014. 1 changed file with 6 additions and 10 deletions.
    16 changes: 6 additions & 10 deletions permut.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    /*
    * Print all permutations of string ``s´´. (C++)
    * Print all permutations of string ``s´´. (C++)
    *
    * Solved as a counting problem and coded in a hurry.
    *
    @@ -36,18 +36,14 @@ bool zero(int counts[MAX])
    }

    /*
    * Are all numbers unique?
    *
    * Note that this is a slow O(n^2) algorithm,
    * but can be improved to O(n).
    * Are all indices unique?
    */
    bool uniq(int counts[MAX])
    {
    for ( int p=0; p<MAX; ++p )
    for ( int i=p+1; i<MAX; ++i )
    if ( counts[p] == counts[i] )
    return false;
    return true;
    int x = 0;
    for ( int n=0; n<MAX; ++n )
    x ^= counts[n] ^ n;
    return x == 0;
    }

    int main()
  3. cslarsen revised this gist Jun 30, 2010. 1 changed file with 6 additions and 0 deletions.
    6 changes: 6 additions & 0 deletions permut.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -35,6 +35,12 @@ bool zero(int counts[MAX])
    return true;
    }

    /*
    * Are all numbers unique?
    *
    * Note that this is a slow O(n^2) algorithm,
    * but can be improved to O(n).
    */
    bool uniq(int counts[MAX])
    {
    for ( int p=0; p<MAX; ++p )
  4. cslarsen renamed this gist Jun 30, 2010. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.txt → permut.cpp
    View file
    File renamed without changes.
  5. cslarsen revised this gist Jun 30, 2010. 1 changed file with 3 additions and 2 deletions.
    5 changes: 3 additions & 2 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -46,10 +46,11 @@ bool uniq(int counts[MAX])

    int main()
    {
    int counts[MAX] = {0, 0, 0};
    int counts[MAX] = {0};

    do {
    if ( uniq(counts) ) print(counts);
    if ( uniq(counts) )
    print(counts);
    inc(counts);
    } while ( !zero(counts) );
    }
  6. cslarsen revised this gist Jun 30, 2010. 1 changed file with 5 additions and 0 deletions.
    5 changes: 5 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,10 @@
    /*
    * Print all permutations of string ``s´´. (C++)
    *
    * Solved as a counting problem and coded in a hurry.
    *
    * A more elegant and recursive solution:
    * http://nicolas-lara.blogspot.com/2009/01/permutations.html
    */

    #include <stdio.h>
  7. cslarsen revised this gist Jun 30, 2010. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    /*
    * Print all permutations of string ``s´´.
    * Print all permutations of string ``s´´. (C++)
    */

    #include <stdio.h>
  8. cslarsen created this gist Jun 30, 2010.
    50 changes: 50 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,50 @@
    /*
    * Print all permutations of string ``s´´.
    */

    #include <stdio.h>

    static const char s[] = "abc";
    const int MAX = (sizeof(s)/sizeof(char)) - 1;

    void print(int counts[MAX])
    {
    for ( int n=0; n<MAX; ++n )
    printf("%c", s[counts[n]]);
    printf("\n");
    }

    void inc(int counts[MAX], int p = 0)
    {
    if ( p < MAX && ++counts[p] >= MAX ) {
    counts[p] = 0;
    inc(counts, p+1);
    }
    }

    bool zero(int counts[MAX])
    {
    for ( int p=0; p < MAX; ++p )
    if ( counts[p] != 0 )
    return false;
    return true;
    }

    bool uniq(int counts[MAX])
    {
    for ( int p=0; p<MAX; ++p )
    for ( int i=p+1; i<MAX; ++i )
    if ( counts[p] == counts[i] )
    return false;
    return true;
    }

    int main()
    {
    int counts[MAX] = {0, 0, 0};

    do {
    if ( uniq(counts) ) print(counts);
    inc(counts);
    } while ( !zero(counts) );
    }