จัดเรียง 1..N ให้ความต่างสัมบูรณ์ของตัวติดกัน > 1 ในภาษา C

หา permutation ของ 1..N ที่ |a[i] - a[i+1]| > 1 สำหรับทุก i ไม่มีคืน -1

วิธี Greedy

เรียงเลขคี่จากมากไปน้อย แล้วตามด้วยเลขคู่จากมากไปน้อย

N=1: [1]

N=2,3: ไม่มีคำตอบ (-1)

N≥4: วิธีนี้ทำงานได้เสมอ

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

void arrange(int N) {
    if (N == 1) { cout << 1; return; }
    if (N == 2 || N == 3) { cout << -1; return; }
    
    int odd = (N%2) ? N : N-1;
    int even = (N%2) ? N-1 : N;
    
    while (odd >= 1) { cout << odd << " "; odd -= 2; }
    while (even >= 2) { cout << even << " "; even -= 2; }
}

int main() {
    arrange(8);
    return 0;
}

ผลลัพธ์

7 5 3 1 8 6 4 2