challenge アレイのuniq

アレイ(複数の値が配列状になっているもの)xsが与えられたときに、同じ値が2回以上出現しないように、2回目以降の出現を取り除いたアレイを返すコードを書いてください。

Rubyで表現すると下のようになります。

irb(main):001:0> xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
=> [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
irb(main):002:0> xs.uniq
=> [3, 1, 4, 5, 9, 2, 6, 8, 7]

間違えないように:よくある「ハッシュを使う」「集合オブジェクトを使う」などの方法は順番が乱れてしまうので使えません。出現順序を守りつつ、2回目以降の出現だけを取り除いてください。

この投稿は匿名での挑戦状の投稿を元に作成しています。ご投稿ありがとうございます。

Posted feedbacks - Nested

Flatten Hidden
「Rubyからの挑戦状」ということで。
1
xs.uniq
うーん。プリミティブ値だけの配列だったらこれでいける。
でも、オブジェクトとかが入ってくると 
toString() の結果によっては正しい結果にならないなあ。

alert([1, 2, 3, 3, 2, 1].uniq()); // [1, 2, 3]
1
2
3
4
5
6
7
Array.prototype.uniq = function () {
  for (var i = 0, r = [], s = {}; i < this.length; i++) {
    if (!s[this[i]]) r.push(this[i]);
    s[this[i]] = true;
  }
  return r;
};
Object Type にも対応した書き方。
効率悪いとか言わない><

alert([1, 2, {}, {}, 2, 1].uniq()); // [1, 2, {}, {}]

var a = {};
alert([1, 2, a, a].uniq()); // [1, 2, {}]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Array.prototype.uniq = function () {
  for (var i = 0, r = [], s = []; i < this.length; i++) {
    for (var j = 0; j < s.length; j ++) 
      if (s[j] === this[i]) break;
    if (j == s.length) {
      r.push(this[i]);
      s.push(this[i]);
    }
  }
  return r;
};
いっそ両方とも実装してみるとか。ダメ?
 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
Array.prototype.uniq = function(usedObjKey) {
  if (typeof(usedObjKey) == 'undefined')
    usedObjKey = (typeof(this[0]) == 'object');
  
  var ret = [];
  if (usedObjKey) {
    for (var i=0, len=this.length, s=[]; i<len; i++) {
      if (s.indexOf(this[i]) < 0) {
        ret.push(this[i]);
        s.push(this[i]);
      }
    }
  }
  else
  {
    for (var i=0, len=this.length, s={}; i<len; i++) {
      if (!s[this[i]])
        ret.push(this[i]);
      s[this[i]] = true;
    }
  }
  return ret;
}

/**
 * @site http://developer.mozilla.org/ja/docs/
 *       Core_JavaScript_1.5_Reference:Global_Objects:Array:indexOf
 */
if (!Array.prototype.indexOf) {
  Array.prototype.indexOf = function(elt /*, from*/) {
    var len = this.length;
    var from = Number(arguments[1]) || 0;
    from = (from < 0) ? Math.ceil(from) : Math.floor(from);
    if (from < 0)
      from += len;
    
    for (; from<len; from++)
      if (from in this && this[from] === elt)
        return from;
    return -1;
  };
}
ObjectやFunctionにも対応してみた。firefox2.0.0.4+Firebugで確認。
なんというかtoJSONString()の手抜き実装みたいだ。
 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
Array.prototype.uniq=function(){
	var h={};
	var tostr=function(obj){
		if(typeof obj == "object"){
			var str="";
			for(var p in obj){
				str+=p+":"+arguments.callee(obj[p]);
			}
			return "{"+str+"}";
		}
		return obj;
	}
	for(var i=0,h={},l=this.length,r=[]; chk=tostr(this[i]),i<l; i++){
		if(!h[chk]===true)r.push(this[i]);
		h[chk]=true;
	}
	return r;
}

// -------------------

var a=[1,2,[3,4],6,2,3,{},{},[4,3]
	,function(){},function(a){},function(){},function(){return this;}
	,{"a":"test1"}
	,{"a":"nest","b":{"c":"nest2"}}
	,{"a":"nest2","b":{"c":"nest3"}}
	,{"a":"nest","b":{"c":"nest2"}}
	,{"a":"test1"}
	,{"a":"test3"}
	,[5,12,4],[4,3],[5]
];
a.uniq();

//[1, 2, [3, 4], 6, 3, Object, [4, 3], function(), function(), function()
//, Object a=test1, Object a=nest b=Object, Object a=nest2 b=Object, Object a=test3
//, [5, 12, 4], [5]]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
require 'pseudohash' # http://www.notwork.org/~gotoken/ruby/p/pseudohash/

xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]

h = PseudoHash.new
xs.each{|i|
  h[i, true] = nil
}
xs_out = h.map{|k, v| k}

p xs_out
効率はともかく
1
2
>>> [ xs[i] for i in xrange(0, len(xs)) if xs[i] not in xs[:i] ]
[3, 1, 4, 5, 9, 2, 6, 8, 7]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]

h = {}
xs_out = []
xs.each {|i|
  xs_out << i unless h.key?(i)
  h[i] = nil
}

p xs_out
# uniq [3; 1; 4; 1; 5; 9; 2; 6; 5; 3; 5; 8; 9; 7; 9];;
- : int list = [3; 1; 4; 5; 9; 2; 6; 8; 7]
1
2
3
4
5
6
7
let uniq xs =
  let rec uniq' acc = function
  | [] -> acc
  | y::ys when (List.mem y acc) -> uniq' acc ys
  | y::ys -> uniq' (y::acc) ys
  in
  List.rev (uniq' [] xs)
#456 は「配列状」を緩く解釈してリストを使いましたが、文字通り配列(だけ)を使うとこうなるのかなあと。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
let rec appears_between p q m a =
   if p = q then false
   else
     if a.(p) = m then true
     else appears_between (succ p) q m a

let uniq2 xs = 
  let ys = Array.copy xs in
  let rec move x y =
    if (Array.length xs) = x then
      Array.sub ys 0 y
    else
      if appears_between 0 y xs.(x) ys then
        move (succ x) y
      else
        (ys.(y) <- xs.(x); move (succ x) (succ y))
  in
  move 0 0
関数型ということにこだわらなければこういう手も。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
open System;;
open Array;;

let uniq xs =
    let ars = create (length xs) xs.(0) in
    let i = ref 1 in
    for idx = 1 to (length xs)-1
    do
        if not (exists (fun elem -> xs.(idx) = elem) ars)
        then
            begin
                ars.(!i) <- xs.(idx);
                i := !i+1
            end
        else ()
    done;
    sub ars 0 !i;;
(vector-uniq xs)
=>#(3 1 4 5 9 2 6 8 7)
1
2
3
4
5
6
7
(define xs #(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9))

(define (vector-uniq vec)
  (let ((ls (vector->list vec)))
    (do ((ls ls (cdr ls))
         (acc '() (if (memv (car ls) acc) acc (cons (car ls) acc))))
        ((null? ls) (list->vector (reverse! acc))))))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import java.util.ArrayList;
import java.util.List;

public class Unique {
	
	public static Object[] toUniqueArray(Object[] array) {
		List unique = new ArrayList();
		for (Object o : array) {
			if (!unique.contains(o)) {
				unique.add(o);
			}
		}
		return unique.toArray();
	}

}
Squeak Smalltalk の #addIfNotPresent: を使って。
1
2
3
4
5
6
7
| xs uniq |
xs := #(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9).
uniq := OrderedCollection new.
xs do: [:each | uniq addIfNotPresent: each].
^uniq asArray

"=> #(3 1 4 5 9 2 6 8 7) "
普通に。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def iter_uniq(it):
    s = set()
    for x in it:
        if x not in s:
            yield x
            s.add(x)

def uniq(a):
    return list(iter_uniq(a))

print uniq([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9])
「hashを使」います。 vectorでもlistでもsequenceなら効きます。
1
2
3
4
5
6
(use gauche.sequence)
(define (uniq a)
  (let1 h (make-hash-table 'equal?)
    (define (p x) (or (hash-table-exists? h x)
                      (begin (hash-table-put! h x #t) #f)))
    (remove-to (class-of a) p a)))
そのものズバリ array_unique を利用。 何のヒネリも有りませんね。
1
2
3
4
<?php
$xs = array(3,1,4,1,5,9,2,6,5,3,5,8,9,7,9);
var_dump(array_unique($xs));
?>
#457や#462を思いつけるようになりたい。
1
2
3
4
5
6
7
8
(define (uniq lst)
  (fold
   (lambda (e l)
     (cond ((null? l) (cons e l))
           ((member e l) l)
           (else (append l (list e)))))
   '()
   lst))
こちらこそ。foldを使うなんて思い付きませんorz
リストの処理で、foldを使うのならこういうのも。最後にreverseするのが残念な感じですが。!無しで。
1
2
3
4
5
6
(define (uniq a)
  (reverse
    (fold (lambda (e knil)
            (if (member e knil)
              knil
              (cons e knil))) () a)))
毎回 (null? l) する無駄や (append l (list e)) あたりの汚さが
消えてすっきりキレイに!
なるほど納得。ありがとうございます。
こんなのでいいのか。 (import Data.List が必要)
1
nub xs
nub だと最悪のケースでO(n^2) になる。以下のuniqなら要素がOrd(順序)クラス
という条件のもとで最悪ケースでO(n log n)にできる。

最悪ケースのベンチマークは以下のとおり

*Main> length $ uniq [1..10000]
10000
(0.13 secs, 11539780 bytes)
*Main> length $ uniq [1..100000]
100000
(1.00 secs, 121637004 bytes)
*Main> length $ nub [1..10000]
10000
(0.98 secs, 1045976 bytes)
*Main> length $ nub [1..100000]
100000
(95.85 secs, 8910200 bytes)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import Data.List

app o f x y = f x `o` f y
cmpapp = app compare
eqapp  = app eq

uniq :: Ord a => [a] -> [a]
uniq  = map snd  . sort . map head . groupBy (eqapp snd) . sortBy (cmpapp snd) . zip [1..]

uniq' :: Eq a => [a] -> [a]
uniq' = nub
あれあれコードを写しそこねてる。ごめんなさい。
eq なんて関数ないし、型宣言を文脈をつけて書くのが正しい。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import Data.List

app :: (b -> b -> c) -> (a -> b) -> (a -> a -> c)
app o f x y = f x `o` f y

cmpapp :: Ord b => (a -> b) -> (a -> a -> Ordering)
cmpapp = app compare

eqapp :: Eq b => (a -> b) -> (a -> a -> Bool)
eqapp  = app (==)

uniq :: Ord a => [a] -> [a]
uniq  = map snd  . sort . map head . groupBy (eqapp snd) . sortBy (cmpapp snd) . zip [1..]
隙があったのでinject
1
2
xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
xs.inject([]){|a, e| a.member?(e) ? a : a << e }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
using System;
using System.Collections.Generic;
class Program
{
  static void Main()
  {
    int[] xs ={ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 };
    foreach(int i in Uniq(xs))
      Console.WriteLine(i);
  }
  static List<T> Uniq<T>(T[] xs)
  {
    List<T> lst = new List<T>();
    Dictionary<T, object> dic = new Dictionary<T, object>();
    foreach (T t in xs) if (!dic.ContainsKey(t))
      { lst.Add(t); dic.Add(t, null); }
    return lst;
  }
}
元の配列をそのまま変更しています。
 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
#include <stdio.h>

int main()
{
  int xs[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
  int array_size;
  int i, j, k;
  int save;

  array_size = (sizeof(xs) / sizeof(xs[0]));
  for (i = 0; i < array_size; i++) {
    save = xs[i];
    for (j = i+1; j < array_size; j++) {
      if (save == xs[j]) {
        /* 配列を詰める作業 */
        for (k = j; k < array_size-1; k++) {
          xs[k] = xs[k+1];
        }
        array_size--;
      }
    }
  }

  for (i = 0; i < array_size; i++) {
    printf("%d ", xs[i]);
  }
  printf("\n");

  return 0;
}
重複を取り除いた配列ということで教科書通りにArrayList.Contains()です。
VS2005なのでムダにジェネリックで。
Javaとほぼ同じロジックなのはナイショだ。つーかC#出てた orz
 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;
using System.Text;

namespace ArrayUniq
{
    class Program
    {
        static void Main(string[] args)
        {
            object[] source = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 };
            object[] results = Uniq(source);
            foreach (object value in results)
            {
                System.Console.WriteLine(value);
            }
        }

        static object[] Uniq(object[] array)
        {
            List<object> uniqList = new List<object>();
            foreach (object value in array)
            {
                if (! uniqList.Contains(value))
                {
                    uniqList.Add(value);
                }
            }
            return uniqList.ToArray();
        }
    }
}
C#からRubyへ感覚を移行する練習です。
1.foreach, Containsのまま移植
2.injectを使いローカル変数を使用せずオブジェクトを返す(#467)
3.uniqメソッドを使用(#448) 
全て同じ結果になります。

Hackety Hackにて作成/実行
http://hacketyhack.net/
http://www.radiumsoftware.com/0705.html#070515
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]

# C#の例(#470)をそのままRubyに変換
us = []
xs.each do |x|
  unless us.member?(x)
    us << x
  end
end
p us

# moroさん(#467) injectを使いローカル変数を使用せずオブジェクトを返す
p xs.inject([]){|a, e| a.member?(e) ? a : a << e }

# 匿名さん(#448) uniqメソッドを使用
p xs.uniq
適当
1
2
(let ((xs (list 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9)))
  (delete-duplicates xs :from-end t))