Aide "sort" d'index trop facile, mais je n'y arrive pas

bonjour,

j’ai un array, par exemple

a = [ 10, 2, 20, 14, 33]

je veux obtenir:

ordre = [5, 3, 4, 1, 2]

je suis sûr que ça s’écrit en une toute petite ligne propre… je
n’arrive qu’à le faire en compliqué, tordu, moche …

merci

Je ne vois pas de rapport entre les deux tableaux…

Je ne vois pas de rapport entre les deux tableaux…

Moi non plus :-/
C’est un test de QI ? :wink:


IciMarché fédère l’e-commerce de proximité
http://icimarche.fr

merci de votre intérêt…

a = [ 10, 2, 20, 14, 33]

un tri descendant donne

a_trié = [ 33, 20, 14, 10, 2]

mais je veux un tri des index (et je les fais commencer à 1 et pas 0)

on avait [1-10, 2-2, 3-20, 4-14, 5-33]
on a [5-33, 3-20, 4-14, 1-10, 2-2]

donc avec seulement les index:

ordre = [5, 3, 4, 1, 2]

voilà, j’espère que c’est plus clair

On 7 mai, 11:27, “Michel B.” [email protected]

Quelque chose comme ca?

a = [ 10, 2, 20, 14, 33]
i = [ 1, 2, 3, 4, 5 ]
i.sort{|i1, i2| a[i2-1] <=> a[i1-1] }

Le 7 mai 2008 11:37, pierrederome [email protected] a écrit :

mais je veux un tri des index (et je les fais commencer à 1 et pas 0)

On 7 mai, 11:27, “Michel B.” [email protected]
wrote:

Je ne vois pas de rapport entre les deux tableaux…


Baptiste

Si, il veut trier le tableau, puis obtenir l’ordre des clés initiales.

Le 7 mai 2008 11:24, pierrederome a écrit :

je suis sûr que ça s’écrit en une toute petite ligne propre… je
n’arrive qu’à le faire en compliqué, tordu, moche …

Mon idée sur laquelle je partirai, serait de trier a par ordre
décroissant et d’effectuer exactement les mêmes opérations
(par exemple de permutation) sur [1, 2, 3, 4, 5].

à toi de prendre un algo de tri le plus
adapté.
– Jean-François.


RailsCamp Paris le samedi 17 mai 2008 :
http://rubyfrance.org/evenements/railscamp-paris

hello,

je te propose ceci (d’autres amélioreront peut être! c’est le ruby
quizz de l’après midi):

irb(main):037:0> a
=> [10, 2, 20, 14, 33]
irb(main):038:0> a.map { |e| a.sort.index(e)+1 }.reverse
=> [5, 3, 4, 1, 2]

bon après midi

Thibaut

http://blog.logeek.fr - learning content for developers
http://evolvingworker.com - tools for a better day

a.map { |e| a.sort.index(e)+1 }.reverse

C’est élégant en effet.

Pour optimiser, on pourrait faire :
b = a.sort
a.map { |e| b.index(e) + 1 }.reverse

Si le tableau est grand ça accélèrera pas mal.

Sinon ça ne marchera pas avec des doublons…

Le 7 mai 2008 11:44, Thibaut Barrère a écrit :

=> [5, 3, 4, 1, 2]
à la louche, on dirait que ça a une complexité en O(n^2), non ?
Et tu tries a à chaque itération…

– Jean-François


Vice-président de l’association Ruby France.
RailsCamp Paris le samedi 17 mai 2008 :
http://rubyfrance.org/evenements/railscamp-paris

Le 7 mai 2008 11:43, Baptiste D. a écrit :

Quelque chose comme ca?

a = [ 10, 2, 20, 14, 33]
i = [ 1, 2, 3, 4, 5 ]
i.sort{|i1, i2| a[i2-1] <=> a[i1-1] }

Ouais, c’est mieux que mon idée puisque là c’est Ruby qui trie à
notre place :slight_smile:

Du coup, on peut faire :

i.sort_by { |i| a[i-1] }

les transformations schwartziennes sont vos amies :slight_smile:

– Jean-François.


RailsCamp Paris le samedi 17 mai 2008 :
http://rubyfrance.org/evenements/railscamp-paris

à la louche, on dirait que ça a une complexité en O(n^2), non ?
Et tu tries a à chaque itération…

Ah oui ça c’est tout moi: je ne cherche à optimiser que si le besoin
apparaît.

– Thibaut

Du coup, on peut faire :

i.sort_by { |i| a[i-1] }

les transformations schwartziennes sont vos amies :slight_smile:

En fait c’était pour trier directement par ordre décroissant sans
avoir à utiliser de reverse.
Mais je n’avais jamais pensé à utiliser sort_by de cette facon, je retiens
:slight_smile:

Joli quizz!

Baptiste

Thibaut Barrère wrote the following on 07.05.2008 11:44 :

hello,

je te propose ceci (d’autres amélioreront peut être! c’est le ruby
quizz de l’après midi):

irb(main):037:0> a
=> [10, 2, 20, 14, 33]
irb(main):038:0> a.map { |e| a.sort.index(e)+1 }.reverse
=> [5, 3, 4, 1, 2]

Ca ne marche pas si tu as deux éléments identiques dans le tableau de
départ (sans compter que faire un sort + index pour chaque entrée du
tableau va vite devenir prohibitif).

a = [ 10, 2, 20, 14, 33 ]
b = []
a.each_with_index { |v,i| b[i] = [ v, i + 1 ] }
b.sort_by { |o| o[0] }.map { |v| v[1] }

=> [2, 1, 4, 3, 5]

On peut s’en sortir en une ligne avec map_with_index qui existe dans
Ruby 1.9 (et dans certaines gems) si j’ai bonne mémoire :

a.map_with_index { |v,i| [ v, i + 1 ] }.sort_by { |o| o[0] }.map { |v|
v[1] }

Lionel

i.sort_by { |i| a[i-1] }

J’aime beaucoup!

– Thibaut

merci beaucoup,
vous êtes top !

à la fin, j’ai fait:

b = []
a.each_with_index { |v,i| b[i] = [ v, i ] }
@ordre=b.sort_by { |o| o[0] }.map { |v| v[1] }.reverse

et c’est nickel, effectivement j’ai ruby 1.8 et pas 1.9

je suis content d’avoir demandé pcq je n’aurais pas fait si simple, et
j’ai appris des trucs !

Ah oui ça c’est tout moi: je ne cherche à optimiser que si le besoin apparaît.

Et pour le savoir, on gagnera à affiner la “compréhension du besoin”
en demandant au client (Pierre):

  • combien d’éléments y-a-t-il dans ton tableau, en moyenne ?
  • peut-il y avoir des doublons ?

– Thibaut

On 07 May 2008, at 11:59, Lionel B. wrote:

On peut s’en sortir en une ligne avec map_with_index qui existe dans
Ruby 1.9 (et dans certaines gems) si j’ai bonne mémoire :

a.map_with_index { |v,i| [ v, i + 1 ] }.sort_by { |o| o[0] }.map { |v|
v[1] }

J’arrive un peu après la bataille :slight_smile: mais si vous voulez faire ça avec
ruby 1.8, vous pouvez faire:

a.enum_with_index.map {|v, i| … }

Problème intéressant en tout cas.

Ca me fait un peu penser à http://www.rubyquiz.com/ .


Jean-Baptiste E.
Belighted.com | Web 2.0 Consulting & Training
Email : [email protected] | Phone: +32 486 377593

Le 7 mai 2008 13:31, Jean-Baptiste E. a écrit :

On 07 May 2008, at 11:59, Lionel B. wrote:

On peut s’en sortir en une ligne avec map_with_index qui existe dans
Ruby 1.9 (et dans certaines gems) si j’ai bonne mémoire :

a.map_with_index { |v,i| [ v, i + 1 ] }.sort_by { |o| o[0] }.map { |v|
v[1] }

je trouve … sort_by { |o| o.first }.map { |v| v.last }

un poil plus long mais nettement plus lisible.

J’arrive un peu après la bataille :slight_smile: mais si vous voulez faire ça avec
ruby 1.8, vous pouvez faire:

a.enum_with_index.map {|v, i| … }

il faut faire un require ‘enumerator’ au préalable.

En 1.9, sans avoir à faire de require, on a l’élégant :

a.map.with_index { |v, i| … }

-- Jean-François.


RailsCamp Paris le samedi 17 mai 2008 :
http://rubyfrance.org/evenements/railscamp-paris

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs