Рубрики

Перестановка элементов массива в следующем порядке

Перестановка — это перестановка членов последовательности в новую последовательность. Например, существует 24 перестановки [a, b, c, d] . Некоторые из них [b, a, d, c] , [d, a, b, c] и [a, d, b, c] .
Перестановка может быть определена массивом P [], где P [i] представляет местоположение элемента по индексу i в перестановке.

Например, массив [3, 2, 1, 0] представляет перестановку, которая отображает элемент с индексом 0 на индекс 3, элемент с индексом 1 на индекс 2, элемент с индексом 2 на индекс 1 и элемент на индекс 3 для индекса 0.

Учитывая массив arr [] из N элементов и массив перестановок P [] , задача состоит в том, чтобы переставить заданный массив arr [] на основе массива перестановок P [] .

Примеры:

Input: arr[] = {1, 2, 3, 4}, P[] = {3, 2, 1, 0}
Output: 4 3 2 1

Input: arr[] = {11, 32, 3, 42}, P[] = {2, 3, 0, 1}
Output: 3 42 11 32

Подход: каждая перестановка может быть представлена набором независимых перестановок, каждая из которых является циклической, то есть она перемещает все элементы с фиксированным смещением, окружающим их. Чтобы найти и применить цикл, который указывает на запись i , просто продолжайте идти вперед (от i к P [i] ), пока мы не вернемся к i . После завершения текущего цикла найдите другой цикл, который еще не был применен. Чтобы проверить это, вычтите n из P [i] после его применения. Это означает, что если запись в P [i] отрицательна, мы выполнили соответствующее движение.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция перестановки заданного
// массив на основе заданных условий

int permute(int A[], int P[], int n)

{

    // Для каждого элемента P

    for (int i = 0; i < n; i++) {

        int next = i;

  

        // Проверить, если это уже

        // рассматривается в цикле

        while (P[next] >= 0) {

  

            // Меняем текущий элемент в соответствии

            // к перестановке в P

            swap(A[i], A[P[next]]);

            int temp = P[next];

  

            // Вычитаем n из записи в P

            // сделать его отрицательным, что указывает

            // соответствующий ход

            // выполнено

            P[next] -= n;

            next = temp;

        }

    }

}

  
// Код драйвера

int main()

{

    int A[] = { 5, 6, 7, 8 };

    int P[] = { 3, 2, 1, 0 };

    int n = sizeof(A) / sizeof(int);

  

    permute(A, P, n);

  

    // Распечатать новый массив после

    // применяем перестановку

    for (int i = 0; i < n; i++)

        cout << A[i] << " ";

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

  
// Функция перестановки заданного
// массив на основе заданных условий

static void permute(int A[], int P[], int n)

{

    // Для каждого элемента P

    for (int i = 0; i < n; i++)

    {

        int next = i;

  

        // Проверить, если это уже

        // рассматривается в цикле

        while (P[next] >= 0)

        {

  

            // Меняем текущий элемент в соответствии

            // к перестановке в P

            swap(A, i, P[next]);

            int temp = P[next];

  

            // Вычитаем n из записи в P

            // сделать его отрицательным, что указывает

            // соответствующий ход

            // выполнено

            P[next] -= n;

            next = temp;

        }

    }

}

  

static int[] swap(int []arr, int i, int j)

{

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

    return arr;

  
// Код драйвера

public static void main(String[] args)

{

    int A[] = { 5, 6, 7, 8 };

    int P[] = { 3, 2, 1, 0 };

    int n = A.length;

  

    permute(A, P, n);

  

    // Распечатать новый массив после

    // применяем перестановку

    for (int i = 0; i < n; i++)

        System.out.print(A[i]+ " ");

  
}
}

  
// Этот код предоставлен 29AjayKumar

Python 3

# Python 3 реализация подхода

  
# Функция перестановки данных
# массив на основе заданных условий

def permute(A, P, n):

      

    # Для каждого элемента P

    for i in range(n):

        next = i

  

        # Проверьте, если это уже

        # считается в цикле

        while (P[next] >= 0):

              

            # Поменять текущий элемент в соответствии

            # к перестановке в P

            t = A[i]

            A[i] = A[P[next]]

            A[P[next]] = t

              

            temp = P[next]

  

            # Вычтите n из записи в P

            # сделать его отрицательным, что указывает

            # соответствующий ход

            # выполнено

            P[next] -= n

            next = temp

  
# Код драйвера

if __name__ == '__main__':

    A = [5, 6, 7, 8]

    P = [3, 2, 1, 0]

    n = len(A)

  

    permute(A, P, n)

  

    # Распечатать новый массив после

    # применение перестановки

    for i in range(n):

        print(A[i], end = " ")

          
# Этот код предоставлен Surendra_Gangwar

C #

// C # реализация подхода

using System;

  

class GFG 

      

    // Функция перестановки заданного

    // массив на основе заданных условий

    static void permute(int []A, int []P, int n) 

    

        // Для каждого элемента P

        for (int i = 0; i < n; i++) 

        

            int next = i; 

      

            // Проверить, если это уже

            // рассматривается в цикле

            while (P[next] >= 0) 

            

      

                // Меняем текущий элемент в соответствии

                // к перестановке в P

                swap(A, i, P[next]); 

                int temp = P[next]; 

      

                // Вычитаем n из записи в P

                // сделать его отрицательным, что указывает

                // соответствующий ход

                // выполнено

                P[next] -= n; 

                next = temp; 

            

        

    

      

    static int[] swap(int []arr, int i, int j) 

    

        int temp = arr[i]; 

        arr[i] = arr[j]; 

        arr[j] = temp; 

        return arr; 

    

      

    // Код драйвера

    public static void Main() 

    

        int []A = { 5, 6, 7, 8 }; 

        int []P = { 3, 2, 1, 0 }; 

        int n = A.Length; 

      

        permute(A, P, n); 

      

        // Распечатать новый массив после

        // применяем перестановку

        for (int i = 0; i < n; i++) 

            Console.Write(A[i]+ " "); 

      

    

  
// Этот код предоставлен AnkitRai01

Выход:

8 7 6 5

Сложность времени: O (n)

Рекомендуемые посты:

Перестановка элементов массива в следующем порядке

0.00 (0%) 0 votes