Python/C: Заполните массив из N элементов случайными числами в интервале [1, N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку). Пример: Массив: 3 2 1 4 5

Это задача на построение случайной перестановки чисел от 1 до N. Нужно, чтобы в массиве обязательно встретились все числа 1, 2, …, N ровно по одному разу, но в случайном порядке.

Самый правильный и простой способ — это алгоритм Фишера–Йетса (Fisher–Yates shuffle). Он работает за O(N) и даёт равномерно случайную перестановку.

Идея алгоритма

1. Создаём массив a = [1, 2, 3, ..., N]

2. Затем перемешиваем его:

   • идём с конца массива к началу

   • для каждого элемента i выбираем случайный индекс j от 0 до i

   • меняем a[i] и a[j]

Python решение

Python
Запустить
import random

def random_permutation(n):
    a = list(range(1, n + 1))
    
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)
        a[i], a[j] = a[j], a[i]
    
    return a

# пример
n = 5
print(random_permutation(n))

Пример вывода:

[3, 2, 1, 5, 4]

Альтернативный Python способ (проще, но менее «алгоритмический»)

Python
Запустить
import random

a = list(range(1, N + 1))
random.shuffle(a)

shuffle() внутри как раз использует Fisher–Yates.

C реализация

C
#include 
#include 
#include 

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void shuffle(int arr[], int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        swap(&arr[i], &arr[j]);
    }
}

int main() {
    int n = 5;
    int arr[n];

    srand(time(NULL));

    // заполняем массив 1..N
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }

    shuffle(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Почему это работает

• мы начинаем с гарантированно полного набора 1..N

• каждое число участвует в обменах

• вероятность каждой перестановки одинакова

Итог: задача решается через генерацию последовательности 1..N и её случайное перемешивание алгоритмом Фишера–Йетса или встроенной функцией shuffle.