Ruby Forum Rails France > 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 ?   ;-)

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

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

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 Belleville" <michel.bellevi...@gmail.com>

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 <pierrederome@gmail.com> a écrit :
>  mais je veux un tri des index (et je les fais commencer à 1 et pas 0)
>
>  On 7 mai, 11:27, "Michel Belleville" <michel.bellevi...@gmail.com>
>  wrote:
>
>
> > Je ne vois pas de rapport entre les deux tableaux...
>  >
>



--
Baptiste

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 Decroix 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 :)

Du coup, on peut faire :

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

les transformations schwartziennes sont vos amies :-)

   -- Jean-François.

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

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

> à 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 :-)
>

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 
:-)

Joli quizz!
--
Baptiste

> 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

> 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 !

On 07 May 2008, at 11:59, Lionel Bouton 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 :) 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 Escoyez
Belighted.com | Web 2.0 Consulting & Training
Email : jbe@belighted.com | Phone: +32 486 377593

Le 7 mai 2008 13:31, Jean-Baptiste Escoyez a écrit :
>
>  On 07 May 2008, at 11:59, Lionel Bouton 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 :) 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