重新排列数组，使索引相同的子集的总和与原始数组中的总和不同

本文概述

• C ++
• Java
• Python3

给定一个由N个不同整数组成的数组A[]，任务是重新排列给定数组，使每个大小小于N的同下标非空子集的和不等于它们在原始数组中的和。

例子：

输入：A [] = {1000, 100, 10, 1}
输出：100 10 1 1000
说明：
原始数组A [] = {1000, 100, 10, 1}
最终数组B [] = {100, 10, 1 , 1000}
大小为1的子集：
A [0] = 1000 B [0] = 100
A [1] = 100 B [1] = 10
A [2] = 10 B [2] = 1
A [3] = 1 B [3] = 1000
大小为2的子集：
{A [0], A [1]} = 1100 {B [0], B [1]} = 110
{A [0], A [2]} = 1010 {B [0], B [2]} = 101
{A [1], A [2]} = 110 {B [1], B [2]} = 11
....
同样, 所有相同的索引大小为2的子集的总和不同。
大小3的子集：
{A [0], A [1], A [2]} = 1110 {B [0], B [1], B [2]} = 111
{A [0], A [2 ], A [3]} = 1011 {B [0], B [2], B [3]} = 1101
{A [1], A [2], A [3]} = 111 {B [1] , B [2], B [3]} = 1011
因此, 没有相同索引的子集具有相等的总和。
输入：A [] = {1, 2, 3, 4, 5}
输出：5 1 2 3 4

方法：

这个想法是用一个较小的元素简单地替换除一个数组元素以外的所有数组元素。请按照以下步骤解决问题：

• 成对存储数组元素{A [i], i}.
• 按升序对对数组元素
• 现在, 遍历排序的顺序, 并将每个元素插入其下一个更大元素的原始索引(即, 在索引处)v [(i + 1)％n]。秒)。这样可以确保除索引之外的每个索引现在都具有比其中存储的先前值小的元素。

证明：令S = {arr1, arr2, …, arrk}是子集。如果u最初不属于S, 则在将u插入S时, 子集的总和发生变化。同样, 如果u属于S, 则让S’包含S中不存在的所有元素。这意味着u不属于S’。然后, 根据上述相同的理由, 子集S’的总和与其原始总和不同。

下面是上述方法的实现：

C ++

//C++ Program to implement
//the above approach
#include <bits/stdc++.h>
using namespace std;
 
//Function to rearrange the array such
//that no same-indexed subset have sum
//equal to that in the original array
void printNewArray(vector<int> a, int n)
{
     //Initialize a vector
     vector<pair<int , int>> v;
 
     //Iterate the array
     for ( int i = 0; i <n; i++) {
 
         v.push_back({ a[i], i });
     }
 
     //Sort the vector
     sort(v.begin(), v.end());
 
     int ans[n];
 
     //Shift of elements to the
     //index of its next cyclic element
     for ( int i = 0; i <n; i++) {
         ans[v[(i + 1) % n].second]
             = v[i].first;
     }
 
     //Print the answer
     for ( int i = 0; i <n; i++) {
         cout <<ans[i] <<" " ;
     }
}
 
//Driver Code
int main()
{
     vector<int> a = { 4, 1, 2, 5, 3 };
 
     int n = a.size();
 
     printNewArray(a, n);
 
     return 0;
}

Java

//Java program to implement
//the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
static class pair
{
     int first, second;
     
     pair( int first, int second)
     {
         this .first = first;
         this .second = second;
     }
}
 
//Function to rearrange the array such
//that no same-indexed subset have sum
//equal to that in the original array
static void printNewArray(List<Integer> a, int n)
{
     
     //Initialize a vector
     List<pair> v = new ArrayList<>();
     
     //Iterate the array
     for ( int i = 0 ; i <n; i++)
     {
         v.add( new pair(a.get(i), i));
     }
     
     //Sort the vector
     Collections.sort(v, (pair s1, pair s2) ->
     {
         return s1.first - s2.first;
     });
     
     int ans[] = new int [n];
 
     //Shift of elements to the
     //index of its next cyclic element
     for ( int i = 0 ; i <n; i++)
     {
         ans[v.get((i + 1 ) % n).second] = v.get(i).first;
     }
     
     //Print the answer
     for ( int i = 0 ; i <n; i++)
     {
         System.out.print(ans[i] + " " );
     }
}
 
//Driver Code
public static void main(String args[])
{
     List<Integer> a = Arrays.asList( 4 , 1 , 2 , 5 , 3 );
 
     int n = a.size();
     printNewArray(a, n);
}
}
 
//This code is contributed by offbeat

Python3

# Python3 Program to implement
# the above approach
 
# Function to rearrange the array such
# that no same-indexed subset have sum
# equal to that in the original array
def printNewArray(a, n):
 
     # Initialize a vector
     v = []
 
     # Iterate the array
     for i in range (n):
         v.append((a[i], i ))
     
     # Sort the vector
     v.sort()
 
     ans = [ 0 ] * n
 
     # Shift of elements to the
     # index of its next cyclic element
     for i in range (n):
         ans[v[(i + 1 ) % n][ 1 ]] = v[i][ 0 ]
    
     # Print the answer
     for i in range (n):
         print (ans[i], end = " " )
 
# Driver Code
if __name__ = = "__main__" : 
     a = [ 4 , 1 , 2 , 5 , 3 ]
     n = len (a)
     printNewArray(a, n)
 
# This code is contributed by Chitranayal

输出如下：

3 5 1 4 2

时间复杂度：O(NLogN)

辅助空间：O(N)

---