J'écris un algorithme qui retournera un tableau avec une longueur et un nombre d'inversions déterminés (paires de nombres, où le nombre du côté gauche est plus grand que le nombre du côté droit). C'est à dire. le tableau [3, 1, 4, 2] contient trois inversions (3, 1), (3, 2) et (4, 2). Ainsi, en pratique, lorsqu'on lui donne la longueur de n = 3 et le nombre d'inversions k = 3, l'algorithme devrait générer un tableau [3, 1, 4, 2] (ou un autre tableau qui remplit ces conditions).
Étant donné que le nombre d'inversions est également le nombre de permutations à effectuer pour que le tableau soit trié par ordre croissant, j'ai abordé ce problème en créant un tableau de 1 à n - 1 et en utilisant un algorithme de tri par insertion dans inverse pour faire k swaps.
Cette approche fonctionne très bien pour les entrées plus petites, mais l'algorithme devrait être capable de générer efficacement des tableaux jusqu'à n = 10 ^ 6 et k = n (n-1) / 2 et tout ce qui se trouve entre les deux, donc l'algorithme devrait fonctionner en temps O (n log n) au lieu de O (n ^ 2). Voici le code:
public class Main {
public static void main(String[] args) {
Inversions in = new Inversions();
int[] arr1 = in.generate(4,3);
int[] arr2 = in.generate(4,0);
int[] arr3 = in.generate(4,6);
System.out.println(Arrays.toString(arr1)); // [3,1,4,2]
System.out.println(Arrays.toString(arr2)); // [1,1,1,1]
System.out.println(Arrays.toString(arr3)); // [4,3,2,1]
}
}
Et la classe principale pour tester avec différents tableaux d'entrée:
import java.util.*;
public class Inversions {
public int[] generate(int n, long k) {
// Don't mind these special cases
if (n == 1) {
int[] arr = {1};
return arr;
}
if (k == 0) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1;
}
return arr;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
int inversions = 0;
int i = 0;
while (inversions < k && i < n) {
int j = i - 1;
while (j >= 0 && arr[j] < arr[j + 1] && inversions < k) {
int helper = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = helper;
inversions++;
j--;
}
i++;
}
return arr;
}
}
L'algorithme ne renvoie exactement les mêmes tableaux que les résultats de l'échantillon, mais réussit tous les tests, sauf ceux où la taille d'entrée est très grande. J'ai également essayé différentes variantes avec le tri par fusion, car il fonctionne en O (temps n log n) mais en vain.
Ce serait super si vous avez des idées. Si vous n'êtes pas familier avec Java, peu importe, le pseudocode ou tout autre type de suggestions sont les bienvenus!
7 Réponses :
Si vous inversez les éléments m initiaux du tableau, vous créez des inversions m (m-1) / 2 .
Si vous inversez les éléments m + 1 initiaux, vous créez des inversions m (m + 1) / 2 .
La différence entre ceux-ci n'est que de m .
Donc:
Cela prend O (n) temps, ce qui est mieux que ce dont vous avez besoin.
Comment cela fonctionnera-t-il pour une longueur de tableau d'entrée = 5 et k = 5? Tableau d'origine = [0, 1, 2, 3, 4]; Valeur du plus grand m = 3; Première moitié inversée = [2, 1, 0]; Maintenant, dans le tableau restant [3,4], comment allez-vous déplacer le premier élément de 5-3 = 2 positions? La longueur elle-même n'est que de 2. [4,3] donnera 1 inversion de plus. Donc, l'inversion totale devient 4 et non k = 5.
@Nazil inverse les 3 premiers pour obtenir [2,1,0,3,4] avec 3 inversions. Puis déplacez les 3 2 positions vers la gauche pour obtenir [2,3,1,0,4] avec 5 inversions
Merci @Matt. J'ai eu une implémentation python où je déplace le dernier élément du tableau [2,1,0,3,4] de 2 positions vers la gauche pour obtenir 5 inversions. Résultat = [2, 1, 4, 0, 3]
Un autre algorithme O (n) : Commencez par un tableau trié. Lorsque vous permutez le premier et le dernier élément, vous obtenez des inversions x = 2 * (n-2) + 1 . Considérez ces deux éléments comme fixes et ne travaillez que sur le tableau restant. Si x est trop grand, envisagez un tableau plus petit. Répétez cette opération aussi longtemps que nécessaire.
Code non testé:
for (int first=0, last = n-1; remainingInversions>0; ) {
int x = 2 * (last-first-1) + 1;
if (x <= remainingInversion) {
first++;
last--;
remainingInversion -= x;
} else {
last--; // consider a smaller array
}
}
En fait, chaque fois que vous échangez le dernier élément avec celui qui le précède, le nombre d'inversions augmente. Voici une solution java:
public static int[] generate(int n, long k) {
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = i;
}
long inversions = 0;
int j = (n-1);
int s = 0;
while(inversions < k) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
inversions++;
j--;
if(j == s) {
j = (n-1);
s++;
}
}
return arr;
}
J'ai une implémentation en Python avec une complexité O (n) .
Elle est basée sur deux règles.
m donne des inversions m * (m-1) / 2 . m positions, crée m inversions. def get_m(k):
m=0
while m*(m-1)/2<=k:
m+=1
else:
m-=1
return m
def generate(l, k):
"""
Generate array of length l with k inversions.
"""
# Generate a sorted array of length l
arr = list(range(0,l))
# If no inversions are needed, return sorted array.
if k==0:
return arr
# Find largest m such that m*(m-1)/2 <= k
m=get_m(k)
# Reverse first m elements in the array which will give m*(m-1)/2 inversions
arr = arr[m-1::-1]+arr[m:]
# Calculate for any remaining inversions
remaining_k = k-(m*(m-1)/2)
# For remaining inversions, move the last element to its left by remaining_k
if remaining_k>0:
arr.insert(int(len(arr)-remaining_k - 1), arr[-1])
arr = arr[:-1]
return arr
if __name__ == '__main__':
l = int(sys.argv[1])
k = int(sys.argv[2])
arr = generate(l, k)
print(arr)
@zhong yang: Cela fonctionne bien dans la plage attendue 0 <= k <= n (n-1) / 2 mais il devrait être préférable de lancer une exception ou null si k est hors de cette plage au lieu de renvoyer un tableau!
Il existe un moyen très simple de créer n inversions ... C'est pour déplacer le dernier élément vers l'avant. Ce n'est pas exactement efficace en raison de la mémoire supplémentaire utilisée, mais je ferais quelque chose comme ceci:
Créez un tableau qui est deux fois la longueur n. Remplissez-le du début au milieu avec une sentinelle (c'est-à-dire null) si nous utilisons un Integer [] au lieu de int []. Remplissez-le du milieu, en montant. Ensuite, faites quelque chose comme ci-dessous ... Je suis sûr que j'ai une erreur et d'autres bogues, mais l'idée générale est capturée dans le code ci-dessous.
int start = 0;
int mid = arr.length / 2;
int end = arr.length - 1;
while (v > 0)
{
if (v < (end - mid))
{
arr[start++] = arr[mid + v];
arr[mid + v] = null;
}
else
{
arr[start++] = arr[end];
v -= (end - mid);
end--;
}
}
Nous avons donc un tableau rempli avec les valeurs de départ, un tas de valeurs nulles, puis les valeurs incrémentielles d'origine, avec une qui peut être devenue nulle, et un pointeur "fin" qui pointe vers le milieu de la zone d'origine.
La dernière étape est donc de copier depuis 0 -> endPos, en ignorant les valeurs nulles, vers le tableau final.
Si k> = n - 1, placez l'élément n - 1 en premier dans le tableau, de sorte qu'il soit inversé avec n - 1 éléments; sinon placez-le en dernier dans le tableau, de sorte qu'il soit inversé avec 0 élément. Continuez cette approche gourmande pour déterminer où vont les autres éléments.
Voici une solution qui implémente generate () pour s'exécuter en temps linéaire avec un peu de maths.
public class Inversions {
public static int[] generate(int n, long k) {
int[] array = new int[n];
// locate k in various sums of (n-1), (n-2), ..., 1
int a = (int) Math.sqrt((n * (n - 1) - 2 * k)); // between the sum of [(n-1)+...+(n-a)] and the sum of [(n-1)+...+(n-a-1)]
int b = n - 1 - a; // counts of (n-1), (n-2), ..., (n-a)
int c = (int) (k - n * b + (b * b + b) / 2); // spillover = k - [(n-1)+(n-b)]*b/2;
// put elements in the array
for (int i = 0; i < b; i++) {
array[i] = n - 1 - i;
}
for (int i = b; i < n - 1 - c; i++) {
array[i] = i - b;
}
array[n - 1 - c] = n - 1 - b;
for (int i = n - c; i < n; i++) {
array[i] = i - b - 1;
}
return array;
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
long k = Long.parseLong(args[1]);
for (int i = 0; i < n; i++) {
StdOut.print(generate(n, k)[i] + " ");
}
}
}
Il s’agit techniquement d’un dupliquer Cependant, c'est assez ancien et déjà répondu. Quelqu'un est-il gêné de me dire s'il faut marquer une question avec réponse comme un double ou non? Je supprimerai ce commentaire une fois répondu, je ne sais pas à qui demander