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

struct Node{
    int val;
   struct Node* left, *right;
};

struct Node* newNode(int val) {
    struct Node* node = malloc(sizeof(struct Node));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void inorder(struct Node* root) {
    if (!root) return;
    inorder(root->left);
    printf("%d\n",  root->val);
    inorder(root->right);
}

void inorder2(struct Node* root) {
    struct Node* s[20];
    int pos = -1;
    while(root != NULL || pos >= 0) {
        while(root != NULL) {
            s[++pos] = root;
            root = root->left;
        }
        root = s[pos--];
        printf("%d\n",  root->val);
        root = root->right;
    }
}

void inorder3(struct Node* root) {
    while(root != NULL) {
        if (root->left == NULL) {
            printf("%d\n",  root->val);
            root = root->right;
        } else {
            struct Node* pre = root->left;
            while(pre->right!= NULL && pre->right!= root) {
                pre = pre->right;
            }
            if (pre->right == root) {
                printf("%d\n",  root->val);
                pre->right = NULL;
                root = root->right;
            } else {
                pre->right = root;
                root= root->left;
            }
        }
    }
}

void preorder(struct Node* root) {
    if (!root) return;
    printf("%d\n",  root->val);
    preorder(root->left);
    preorder(root->right);
}

void preorder2(struct Node* root) {
    struct Node* s[100];
    int pos = -1;
    while(root != NULL || pos >= 0) {
        if (root != NULL) {
            printf("%d\n",  root->val);
            s[++pos] = root->right;
            root = root->left;
        } else {
            root = s[pos--];
        }
    }
}

void postorder(struct Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d\n",  root->val);
}
struct item{
    struct Node* node;
    int visiting;
};

struct item * newItem(struct Node* node) {
    struct item * it = malloc(sizeof(struct item));
    it->node = node;
    it->visiting = 1;
    return it;
}

void postorder2(struct Node* root) {
    struct item * s[100];
    int pos = -1;
    while(root != NULL || pos >= 0) {
        if (root != NULL) {
            s[++pos] = newItem(root);
            s[pos]->visiting = 0;
            if (root->right != NULL)
                s[++pos] = newItem(root->right);
            root = root->left;
        } else {
            struct item * it = s[pos--];
            root = it->node;
            if (it->visiting == 1) {
                s[++pos] = newItem(root);
                s[pos]->visiting = 0;
                if (root->right != NULL)
                    s[++pos] = newItem(root->right);
                root = root->left;
            } else {
                printf("%d\n",  root->val);
                root = NULL;
            }
        }
    }
}
#define N 10
void next_permutation(int a[N]) {
    int p1 = -1;
    for(int i=N-1; i>0; --i) {
        if (a[i-1] < a[i]) {
            p1 = i-1;
            break;
        }
    }
    if (p1 == -1) return;
    int p2 = p1 + 1;
    for(int i=p1+1; i<N; ++i) {
        if (a[i] > a[p1] && a[i] < a[p2]) p2 = i;
    }
    int tmp = a[p2];
    a[p2] = a[p1];
    a[p1] = tmp;
    int L,  R;
    L = p1+1;
    R = N-1;
    while(L < R) {
        int tmp = a[R];
        a[R] = a[L];
        a[L] = tmp;
        ++L; --R;
    }
}


void shuffle(int a[N]) {
    for(int i=N-1; i>0; --i) {
        int pos = ((int)rand()) % (i+1);
        // swap a[pos],  a[i]
        int tmp = a[i];
        a[i] = a[pos];
        a[pos] = tmp;
    }
}

void shuffle2(int a[N]) {
    for(int i=1; i<N; ++i) {
        int pos = ((int)rand()) % (i+1);
        // swap a[pos],  a[i]
        int tmp = a[i];
        a[i] = a[pos];
        a[pos] = tmp;
    }
}

int main(int argc, const char *argv[])
{
    int a[10] = {0,  1, 2, 3, 4, 5, 6, 7, 8, 9};
    for(int j=0; j<100; ++j) {
        shuffle2(a);
    for(int i=0; i<N; ++i) {
        printf("%d, ",  a[i]);
    }
    printf("\n");
    }
    return 0;
}