0

The problem is given a permutation of 1,2, …, n, generate the next permutation in lexicographic order. For example, for 2 3 1 4 the answer is 2 3 4 1.

My code is,

void read(int *l, int* size) {
    char buf[2900];
    *size = 0;
    char *in = buf;
    int *out = l;
    //cin.sync();
    cin.getline(buf, 2900);
    do {
        *out = 0;
        while (*in >= '0' && *in <= '9') {
            *out = *out * 10 + (*in - '0');
            in++;
        }
        if (*in)
            in++;
        ++out;
    } while (*in);
    *size = out - l;
}

int main() {
    int N, K;
    cin >> N >> K;
    int in[K][N];
    for (int i = 0; i < K; ++i) {
        int s;
        read(in[i], &s);
    }
    for (int i = 0; i < K; ++i) {
        for (int j = N - 2; j >= 0; --j) {
            int x = in[i][j];
            int s = -1, v = 1000;
            for (int k = j + 1; k < N; k++) {
                if (in[i][k] > x && in[i][k] < v) {
                    s = k;
                    v = in[i][k];
                }
            }
            if (s != -1) {
                int c = in[i][s];
                in[i][s] = x;
                in[i][j] = c;
                sort(in[i] + j + 1, in[i] + N);
                break;
            }
        }
    }
    for (int i = 0; i < K; i++) {
        for (int k = 0; k < N; k++)
            cout << in[i][k] << " ";
        cout << endl;
    }
    return 0;
}

As you can probably say from the code, I am a complete novice. It gives the right answer when I test, but the judge says that it gives wrong answers.

Help?

Thank you!

The Archetypal Paul
  • 41,321
  • 20
  • 104
  • 134
Vaishnav Sreekanth Menon
  • 1
  • 2
    Why not use [`std::next_permutation`](http://en.cppreference.com/w/cpp/algorithm/next_permutation)? – irrelephant Nov 10 '14 at 18:35
  • I must be missing something but from your 1 example I don't get what "the next permutation in lexicographic order" means. Also, don't you have examples of where the code gives incorrect results? – Jan Doggen Nov 10 '14 at 18:36
  • @irrelephant, Because it's an assignment "the judge says that it gives wrong answers." – The Archetypal Paul Nov 10 '14 at 18:42
  • Why do use such a strange way of reading the input data(why don't you use `std::cin` for each number instead)?. – kraskevich Nov 10 '14 at 18:45
  • TLDR, but a simple algorithm can be based on the observation that as you scan from the right, as long as the items are in increasing order they can't be reordered to be more in increasing (final) order, so you have to go on to find the item to move. – Cheers and hth. - Alf Nov 10 '14 at 18:49
  • An algorithm is presented here: http://stackoverflow.com/questions/352203/generating-permutations-lazily/362714#362714 – The Archetypal Paul Nov 10 '14 at 18:50
  • Some comments in your code for the reader, and better variable names would probably help (and help you, too) – The Archetypal Paul Nov 10 '14 at 18:51
  • And how many numbers can be there in the input? It may happen that your input buffer(`buf`) size is just too small. – kraskevich Nov 10 '14 at 18:51
  • @Paul: Nice link. I miss references for the direct computation approach in that answer. I published it as a letter to the editor in "Software Development" in the late 1980's, implemented in Modula-2, where the editor added the title "The third method is the charm", as I recall. The editor also added info that someone at Texas Instruments had already invented this method, of which I was unaware. Knuth did not discuss this approach in his "The Art of Computer Programming", but he did discuss the other two main ways. – Cheers and hth. - Alf Nov 10 '14 at 18:54
  • @Cheersandhth.-Alf, I can't say anything about the references, it's not my answer. – The Archetypal Paul Nov 10 '14 at 18:55
  • Sorry for the late post, but, I wanted to make an algo myself. Lexicographic order as in 1,2,3, 1,3,2, 2,1,3... Unfortunately, the judge didn't give any output except "wrong answer". Great, right? -_- I use that way because the number of numbers to be read is taken in first. Variable input size. you can have a max of 2893 characters or so. I'll check increasing though. right now, I'm a bit short on time. I'll explain the algo later. It's very inefficient :P – Vaishnav Sreekanth Menon Nov 11 '14 at 02:19

0 Answers0