DouKaku?beta

challenge データの整列

(x, y) の座標情報を以下の2種類の方法で整列する機能を実現してください。

  • (x, y) の辞書順(まず x で昇順に整列して、x が同じデータに対して y で昇順に整列する)
  • (0, 0) からの距離の昇順

データの表現方法はタプルなり構造体/オブジェクトなり各自で適当に選んで下さい。

post comment

Posted feedbacks - Nested

Flatten Hidden
こんなかんじでいいのかな？ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using System;
using System.Collections.Generic;
static class Program {
    static void Main(String[] args) {
        List<Pair> plist = new List<Pair>();
        Random rand = new Random();
        for(int i = 0; i < 10; i++) plist.Add(new Pair(rand.Next(5), rand.Next(5)));
        Console.WriteLine("----- 元データ");
        foreach(Pair p in plist) Console.WriteLine(p);
        
        Console.WriteLine("----- 辞書順でソート");
        plist.Sort(delegate(Pair p1, Pair p2) {
            return p1.x != p2.x ? p1.x.CompareTo(p2.x) : p1.y.CompareTo(p2.y);
        });
        foreach(Pair p in plist) Console.WriteLine(p);
        
        Console.WriteLine("----- 距離順でソート");
        plist.Sort(delegate(Pair p1, Pair p2) {
            return (p1.x * p1.x + p1.y * p1.y).CompareTo(p2.x * p2.x + p2.y * p2.y);
        });
        foreach(Pair p in plist) Console.WriteLine(p);
    }
}
class Pair {
    public readonly int x, y;
    public Pair(int x, int y) {
        this.x = x; this.y = y;
    }
    public override string ToString() {
        return "(" + x + ", " + y + ")";
    }
}

Scalaで。

    CoordSort.lexical(List((1,2), (3,4), (1,3), (2,4), (1,8))).toList
    // => List((1,2), (1,3), (1,8), (2,4), (3,4))

    CoordSort.fromOrigin(List((1,2), (3,4), (1,3), (2,4), (1,8))).toList
    // => List((1,2), (1,3), (2,4), (3,4), (1,8))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
object CoordSort {
  import scala.util.Sorting.stableSort
  type Coord = Pair[int,int]

  def sort(f:(int, int, int, int) => boolean, lst:Seq[Coord]) = {
    stableSort(lst, (a:Coord, b:Coord) => f(a._1, a._2, b._1, b._2))
  }

  val lexical = Function.curried(sort _)((ax, ay, bx, by) => 
                  if(ax == bx) { ay < by } else { ax < bx }
                )

  val fromOrigin = Function.curried(sort _)((ax, ay, bx, by) => 
                     (ax*ax + ay*ay) < (bx*bx + by*by)
                   )

}

別に面白いことは何もありませんが、普通に。
   pairlist = []
   10.times { pairlist.push(LexicalPair.new(rand(10), rand(10))) }
   puts pairlist.sort
とかして遊びます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Pair
  attr_reader :x, :y
  def initialize(x,y)
    @x, @y = x, y
  end
  def to_s
    "(#{@x},#{@y})"
  end
end

class LexicalPair < Pair
  include Comparable
  def <=>(p)
    @x == p.x ? @y <=> p.y : @x <=> p.x
  end
end

class PolarPair < Pair
  include Comparable
  def <=>(p)
    (@x**2 + @y**2) <=> (p.x**2 + p.y**2)
  end
end
Common Lispのsort関数は、大小を比較する関数を指定しますが、
比較する関数さえ変更すれば、多様な比較が可能となっています。

sortはリストを破壊的に変更するので、例では、リストをコピーして引数に与えています。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
*positions*
;=>
((9 . 98) (77 . 0) (17 . 30) (17 . 73) (83 . 3) (81 . 30) (99 . 99)
 (90 . 68) (21 . 81) (92 . 29))

;; 辞書順で比較
(sort (copy-list *positions*)
      (lambda (x y) 
        (cond ((< (car x) (car y)) 'T)
              ((= (car x) (car y)) (< (cdr x) (cdr y)))
              ('T nil))))
;=>
((9 . 98) (17 . 30) (17 . 73) (21 . 81) (77 . 0) (81 . 30) (83 . 3)
 (90 . 68) (92 . 29) (99 . 99))


;; (0, 0)からの距離で比較
(sort (copy-list *positions*) 
      #'< :key (lambda (x) (expt (+ (car x) (cdr x)) 1/2)))
;=>
((17 . 30) (77 . 0) (83 . 3) (17 . 73) (21 . 81) (9 . 98) (81 . 30)
 (92 . 29) (90 . 68) (99 . 99))

Ruby です。

set = [ [ 1, 2 ], [ 1, 3 ], [ 2, 8 ], [ 9, 5 ], [ 6, 8 ], [ 0, 2 ] ]
include Coord
p sort_lexical( set )
p sort_distance( set )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
module Coord
  def sort_lexical coords
    coords.sort do | a, b |
      if a[ 0 ] == b[ 0 ]
        a[ 1 ] <=> b[ 1 ]
      else
        a[ 0 ] <=> b[ 0 ]
      end
    end
  end


  def sort_distance coords
    coords.sort do | a, b |
      a[ 0 ] * a[ 0 ] + a[ 1 ] * a[ 1 ] <=> b[ 0 ] * b[ 0 ] + b[ 1 ] * b[ 1 ]
    end
  end
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import Data.List

lexicalOrder (x1, y1) (x2, y2)
  | x1 < x2   = LT
  | x1 > x2   = GT
  | y1 < y2   = LT
  | y1 > y2   = GT
  | otherwise = EQ

lengthOrder (x1, y1) (x2, y2) = 
  let length x y = sqrt $ x**2 + y**2 in
    compare (length x1 y1) (length x2 y2)

sample = [(1,1), (3,3), (0,0), (0,3), (4,0)]

main = do
  print $ sortBy lexicalOrder sample
  print $ sortBy lengthOrder  sample

-- [(0.0,0.0),(0.0,3.0),(1.0,1.0),(3.0,3.0),(4.0,0.0)]
-- [(0.0,0.0),(1.0,1.0),(0.0,3.0),(4.0,0.0),(3.0,3.0)]

普通に。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import random

def main():
    a = [(i, j) for i in xrange(3) for j in xrange(3)]
    random.shuffle(a)

    print "original:"
    print a

    print "dictionary:"
    print sorted(a)

    print "distance:"
    print sorted(a, key=lambda p: p[0] ** 2 + p[1] ** 2)

if __name__ == '__main__':
    main()

OCamlで書いてみた。こんなんでいいのかな。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
type point = Poiont of float * float


let compare_point a b =
  match (a, b) with
    (Point (x1, y2), Point (x2, y2)) -> if x1 = x2 then compare y1 y2
                                                   else compare x1 x2

let distance = function
    Point (x, y) -> sqrt (x *. x +. y *. y)


let sort_by_dic = List.sort compare_point


let sort_by_dis = List.sort (fun a b -> compare (distance a) (distance b))

うわっ，typoしたままのを貼り付けてしまいました（今頃気づいた）。改めて張り直しておきます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
type point = Point of float * float


let compare_point a b =
  match (a, b) with
    (Point (x1, y1), Point (x2, y2)) -> if x1 = x2 then compare y1 y2
                                                   else compare x1 x2

let distance = function
    Point (x, y) -> sqrt (x *. x +. y *. y)


let sort_by_dic = List.sort compare_point


let sort_by_dis = List.sort (fun a b -> compare (distance a) (distance b))

どないだ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#! /bin/perl
use warnings;
use strict;
use Data::Dumper;
my @data = ( [1,2],[5,8],[-2,5] ,[1,6],[4,7]);

print "辞書順\n";
print Dumper [ sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @data ];
print "距離順\n";
print Dumper [sort { $a->[0] ** 2 + $a->[1] ** 2 <=> $b->[0] ** 2 + $b->[1] ** 2} @data];

シンプルにクイックソートで。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
} point;

int compare_val(const point *a, const point *b){
    if (a->x==b->x){
        return a->y-b->y;
    }else{
        return a->x-b->x;
    }
}

int compare_dist(const point *a, const point *b){
    long dist_a,dist_b;
    dist_a=a->x*a->x+a->y*a->y;
    dist_b=b->x*b->x+b->y*b->y;

    if(dist_a==dist_b){
        return compare_val(a,b);
    }else{
        return dist_a-dist_b;
    }
}

int main(){
    point data1[]={
        {0,0},
        {1,0},
        {2,0},
        {0,1},
        {1,1},
        {2,1},
        {0,2},
        {1,2},
        {2,2},
    };
    point data2[]={
        {0,0},
        {1,0},
        {2,0},
        {0,1},
        {1,1},
        {2,1},
        {0,2},
        {1,2},
        {2,2},
    };
    qsort(data1, sizeof(data1)/sizeof(point), sizeof(point), (int (*)(const void*, const void*))compare_val);
    qsort(data2, sizeof(data2)/sizeof(point), sizeof(point), (int (*)(const void*, const void*))compare_dist);

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import std.stdio;
import std.algorithm;

void main(){
    int[][] array = [[1, 3], [-1, 0], [-2, 3], [1, -9], [1, -19],
                     [4, 2], [3, 104], [4, -91]];

    bool lexical(int[] a, int[] b){
        return (a[0] == b[0]) ? (a[1] < b[1]) : (a[0] < b[0]);
    }
    bool distance(int[] a, int[] b){
        return (a[0] * a[0] + a[1] * a[1]) < (b[0] * b[0] + b[1] * b[1]);
    }

    auto a1 = array.dup;
    auto a2 = array.dup;
    sort!(lexical)(a1);
    sort!(distance)(a2);

    writeln(a1);  // [[-2 3] [-1 0] [1 -19] [1 -9] [1 3] [3 104] [4 -91] [4 2]]
    writeln(a2);  // [[-1 0] [1 3] [-2 3] [4 2] [1 -9] [1 -19] [4 -91] [3 104]]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>

struct Pos
{
    double x;
    double y;
    Pos() : x(0), y(0) {}
    Pos(double x, double y) : x(x), y(y) {}
    double length() const { return std::sqrt(x*x + y*y); }
};

bool lexicalOrder(const Pos& lhs, const Pos& rhs)
{
    return (lhs.x  < rhs.x) ||((lhs.x == rhs.x) && (lhs.y < rhs.y));
}

bool lengthOrder(const Pos& lhs, const Pos& rhs)
{
    return lhs.length() < rhs.length();
}

std::ostream& operator << (std::ostream& out, const Pos& pos)
{
    return out << '(' << pos.x <<',' << pos.y << ')';
}

int main(int, char* [])
{
    std::vector<Pos> a;
    a.push_back(Pos(1, 1));
    a.push_back(Pos(3, 3));
    a.push_back(Pos(0, 0));
    a.push_back(Pos(0, 3));
    a.push_back(Pos(4, 0));

    std::sort(a.begin(), a.end(), lexicalOrder);
    std::copy(a.begin(), a.end(), std::ostream_iterator<Pos>(std::cout, " "));
    std::cout << "\n";
    // (0,0) (0,3) (1,1) (3,3) (4,0)

    std::sort(a.begin(), a.end(), lengthOrder);
    std::copy(a.begin(), a.end(), std::ostream_iterator<Pos>(std::cout, " "));
    std::cout << "\n";
    // (0,0) (1,1) (0,3) (4,0) (3,3)

    return 0;
}

座標の値が不変なら、長さをキャッシュして毎回計算しないようにしますよね。(蛇足か...)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
% diff -u 5866.cpp.orig 5866.cpp
--- 5866.cpp.orig    2008-02-27 19:06:45.000000000 +0900
+++ 5866.cpp    2008-02-27 19:10:30.000000000 +0900
@@ -8,9 +8,8 @@
 {
     double x;
     double y;
-    Pos() : x(0), y(0) {}
-    Pos(double x, double y) : x(x), y(y) {}
-    double length() const { return std::sqrt(x*x + y*y); }
+    double length;
+    Pos(double x, double y) : x(x), y(y), length(std::sqrt(x*x + y*y)) {}
 };
 
 bool lexicalOrder(const Pos& lhs, const Pos& rhs)
@@ -20,7 +19,7 @@
 
 bool lengthOrder(const Pos& lhs, const Pos& rhs)
 {
-    return lhs.length() < rhs.length();
+    return lhs.length < rhs.length;
 }

キャッシュなんていう前にsqrtが本当に
必要なのか考えた方がよさそう。

	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function Point(x, y){
    this.x=x;
    this.y=y;
    this.size=Math.sqrt(x*x+y*y);
    this.toString=function(){ return "(" + this.x + "," + this.y + ")" }
}

var data = new Array(
    new Point(0,0),
    new Point(1,0),
    new Point(2,0),
    new Point(0,1),
    new Point(1,1),
    new Point(2,1),
    new Point(0,2),
    new Point(1,2),
    new Point(2,2)
);

data.sort(function(a,b){ return(a.size - b.size) });
print(data.join());
data.sort(function(a,b){ return (a.x == b.x) ? a.y - b.y :a.x - b.x });
print(data.join());




    

	

  
  








  


  

  
    







  
  

	

	  
匿名さんのとほとんど同じですが、微妙な違いとして：
１．辞書順は実は言語サポートがある。
２．distをData.Function.on :: (b -> b -> c) -> (a -> b) -> a -> a -> cを使って適用している。

ところ*だけ*違います。何かのお役に立てば...


	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
module Main
    where

import Data.List
import Data.Function

byDist :: (Int, Int) -> (Int, Int) -> Ordering
byDist x y = on compare dist x y
    where
        dist (x, y) = x * x + y * y

sortByDict as = sort as
sortByDist as = sortBy byDist as

main = do
    putStrLn $ show lstOrig
    putStrLn "Sort by distance"
    putStrLn.show $ sortByDist lstOrig
    putStrLn "Sort by dictionary order"
    putStrLn.show $ sortByDict lstOrig
    where
        lstOrig = [(1, 2), (2, 1), (4, 30), (9, 0), (-1, -10)]




    

	

  
  








  


  

  
    







  
  

	

	  
	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
<?php
#元データ
$list = array(
    array( "x"=>3,"y"=>3)
    ,array( "x"=>2,"y"=>10)
    ,array( "x"=>2,"y"=>1)
    ,array( "x"=>1,"y"=>2)
    ,array( "x"=>1,"y"=>1)
    ,array( "x"=>3,"y"=>1)
    ,array( "x"=>1,"y"=>10)
);

#辞書順
usort(
    $list,
    create_function(
        '$a,$b',
        'return ($a["x"] == $b["x"]) ? ($a["y"] > $b["y"]) : ($a["x"] > $b["x"] );'
    )
);
var_dump($list);
#距離順
usort(
    $list,
    create_function(
        '$a,$b',
        'return pow($a["x"],2)+pow($a["y"],2) > pow($b["x"],2)+pow($b["y"],2);'
    )
);
var_dump($list);
?>




    

	

  
  








  
    

      
      







  
  

	

	  
PHPをOtherとして投稿してしまいました。すいません。


	

	
	
	

  
  








  


    

  


  

  
    







  
  

	

	  
括弧多めで。


	

	
	
	
    

      
1
2
3
4
5
6
import Data.List

sample = [(1, 1), (3, 3), (0, 0), (0, 3), (4, 0)]
  
main = do (print . sort) sample
          (print . sortBy (\(a, b) (c, d) -> compare (a**2+b**2) (c**2+d**2))) sample




    

	

  
  








  


  

  

  
    







  
  

	

	  
やっつけコード。


	

	
	
	
    

      
1
2
let dict_sort = List.sort (fun (x1,x2) (y1,y2) -> match x1 - y1 with 0 -> x2 - y2 | d -> d);;
let dist_sort = List.sort (fun (x1,x2) (y1,y2) -> (x1*x1 + x2*x2) - (y1*y1 + y2*y2));;




    

	

  
  








  


  

  
    







  
  

	

	  
２値の配列で座標を表現して、その配列をソートします。


	

	
	
	
    

      
1
2
3
4
5
6
coordinates = Array.new(10) { [rand(10), rand(10)]}

# by dictionary
p coordinates.sort
# by distance
p coordinates.sort {|(x1, y1), (x2, y2)| (x1**2 + y1**2) <=> (x2**2 + y2**2) }




    

	

  
  








  
    

      
      







  
  

	

	  
すいません言語指定し忘れました。
Rubyです。


	

	
	
	

  
  








  


    

  


  

  

  
    







  
  

	

	  
Javaらしく、Comparatorを実装しました。


	

	
	
	
    

      
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class Sample163 {
    public static void main(String[] args) {
        Random random = new Random();
        List<Point> list = new ArrayList<Point>();
        for (int index = 0, count = 10; index < count; index++) {
            list.add(new Point(random.nextInt(10), random.nextInt(10)));
        }

        System.out.print("original  : ");
        System.out.println(list.toString());

        Collections.sort(list, new DictionaryComparator());
        System.out.print("dictionary: ");
        System.out.println(list.toString());

        Collections.sort(list, new DistanceComparator());
        System.out.print("distance  : ");
        System.out.println(list.toString());
    }
}

class Point {
    public final int x;
    public final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override public String toString() {
        return "(" + x + "," + y + ")";
    }
}

class DictionaryComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        int result = Integer.valueOf(o1.x).compareTo(o2.x);
        if (result == 0) {
            result = Integer.valueOf(o1.y).compareTo(o2.y);
        }
        return result;
    }
}

class DistanceComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        return Integer.valueOf(o1.x * o1.x + o1.y * o1.y).compareTo(o2.x * o2.x + o2.y * o2.y);
    }
}




    

	

  
  








  


  

  
    







  
  

	

	  
実行例:
gosh> (sort-c '((1 . 2) (3 . 5) (4 . 2) (3 . 1) (2 . 7)) 'dic)
((1 . 2) (2 . 7) (3 . 1) (3 . 5) (4 . 2))

gosh> (sort-c '((1 . 2) (3 . 5) (4 . 2) (3 . 1) (2 . 7)) 'dist)
((1 . 2) (3 . 1) (4 . 2) (3 . 5) (2 . 7))

	

	
	
	
    

      
1
2
3
4
5
6
7
(define (sort-c ls sym)
  (cond ((eq? sym 'dic