アレイのuniq DouKaku?

アレイ(複数の値が配列状になっているもの)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回目以降の出現だけを取り除いてください。

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

「Rubyからの挑戦状」ということで。

xs.uniq

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

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

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;
};

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]

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]

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)

(vector-uniq xs)
=>#(3 1 4 5 9 2 6 8 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))))))

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: を使って。

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

普通に。

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なら効きます。

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

Object Type にも対応した書き方。
効率悪いとか言わない＞＜

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

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

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;
};

そのものズバリ array_unique を利用。何のヒネリも有りませんね。

<?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を思いつけるようになりたい。

(define (uniq lst)
  (fold
   (lambda (e l)
     (cond ((null? l) (cons e l))
           ((member e l) l)
           (else (append l (list e)))))
   '()
   lst))

こんなのでいいのか。 (import Data.List が必要)

nub xs

隙があったので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 }

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;
  }
}

元の配列をそのまま変更しています。

#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

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();
        }
    }
}

適当

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

iterateパッケージを使ってみました。これ便利すぎ。

1
2
3

(require :iterate)
(in-package :iterate)
(iter (for x in '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9)) (adjoining x)) ; => (3 1 4 5 9 2 6 8 7)

forEachでまわしてる配列をいじるのってやばいですかね。

var xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9];
xs.forEach(function(i) {
    if (xs.indexOf(i) != xs.lastIndexOf(i))
        xs.splice(xs.lastIndexOf(i), 1)
});
alert(xs);

なんとなく内包表記で。

import sys

def uniq(a):
    s = set()
    def check(x):
        if x not in s:
            s.add(x)
            return True
        else:
            return False
    return [x for x in a if check(x)]

if __name__ == '__main__':
    print uniq([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9])

Emacs22で。

(setq xs [3 1 4 1 5 9 2 6 5 3 5 8 9 7 9])

(vconcat (delete-dups (append xs nil)))
=>[3 1 4 5 9 2 6 8 7]

普通のコードはすでに出てるので無駄に高度なことをしてみる

(let ((xs '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9)))
  (let ((*readtable* (copy-readtable)))
    (flet ((skip (stream char) (declare (ignore char stream)) (values)))
      (flet ((read-digit (stream char)
	       (set-macro-character char #'skip)
	       (parse-integer (string char))))
	(dotimes (c 10)
	  (set-macro-character (code-char (+ 48 c)) #'read-digit))
	(with-input-from-string (s (prin1-to-string xs))
	  (read s))))))

#456 は「配列状」を緩く解釈してリストを使いましたが、文字通り配列（だけ）を使うとこうなるのかなあと。

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

こちらこそ。foldを使うなんて思い付きませんorz

こんな感じかな？ spidermonkey1.6で確認。

Array.prototype.uniq = function() {                                                                                                    
  label_unique:                                                                                                                        
  for(var uniformized = [], i = 0; i < this.length; i++) {                                                                             
    for(var l = 0; l < uniformized.length; l++) if(this[i] === uniformized[l]) continue label_unique;                                  
    uniformized.push(this[i]);                                                                                                         
  }                                                                                                                                    
  return uniformized;                                                                                                                  
}                                                                                                                                      
var xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9];                                                                                
xs.uniq(); // 3,1,4,5,9,2,6,8,7

再帰で

1 2	uniq [] = [] uniq (x:xs) = x:uniq (filter (/=x) xs)

(print (uniq '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9)))
;他の人たちのコードを見てると勉強になります。

(defun uniq (lst)
  (labels ((rec (l acc)
              (if (null l) (reverse acc)
                (let ((top (car l)) (rests (cdr l)))
                  (if (member top acc)
                    (rec rests acc)
                    (rec rests (cons top acc)))))))
    (rec lst nil)))

var xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 5, 5, 5, 5]; みたいな場合にちゃんと動いてませんでした。あう。

たまにはoneliner

1 2	% perl -e 'print join ",", (grep { $tmp{$_}++ == 0 } @ARGV); print "\n"' 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3,1,4,5,9,2,6,8,7

Scala で。バッファが使えるのであまり考えずに書ける。このコードは単体プログラムではなくインタプリタ向け。

import scala.collection.mutable._

def uniq[T](xs: Array[T]): Array[T] = {
  val buffer = new ArrayBuffer[T]
  xs.foreach { e => if (!buffer.contains(e)) buffer + e }
  buffer.toArray
}

初めて投稿してみます。Perl での短めコードを目指してみました。
hash を使って、二度目を表示しないようにしています。

1 2	@xs = (3,1,4,1,5,9,2,6,5,3,5,8,9,7,9); print grep{$_ if!$t{$_}++}@xs;

リストの処理で、foldを使うのならこういうのも。最後にreverseするのが残念な感じですが。!無しで。

(define (uniq a)
  (reverse
    (fold (lambda (e knil)
            (if (member e knil)
              knil
              (cons e knil))) () a)))

いい勉強になりますね。:-) 僕は末尾再帰版で

(defun uniq (list)
  (labels ((uniq-sub (out in)
	     (if (null in)
		 out
		 (uniq-sub (append out (list (car in)))
			   (remove (car in) (cdr in))))))

    (uniq-sub nil list)))

Prologって、マイナーなんだなぁ。

uniq([], R) :- fill(R).
uniq([Xh|Xs], R) :- memv(Xh, R), uniq(Xs, R).
uniq([Xh|Xs], R) :- add(Xh, R), uniq(Xs, R).

memv(_, V) :- var(V), fail.
memv(X, [X|_]).
memv(X, [_|Vt]) :- memv(X, Vt).

add(X, R) :- var(R), R=[X|_].
add(X, [_|Rt]) :- add(X, Rt).

fill(R):-var(R), R=[].
fill([_|Rs]):-fill(Rs).

:- uniq([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9], R), writeln(R).

効率の方を。

Array.prototype.uniq = function () {
  var result = [], prev = {}, value, prev_null = 0, i;
  for (i = 0; i < this.length; ++i) {
    value = this[i];
    typeof value !== 'object'
      ? prev[value] || (prev[value] = 1, result.push(value))
      : value === null
        ? prev_null++ || result.push(null)
        : value === void(0) || value.__prev || (value.__prev = true, result.push(value));
  }
  for (i = 0; i < this.length; ++i) {
    value instanceof Object && delete value.__prev;
  }
  return result;
};

ミスりました。
line 12 value -> this[i]

DouKaku?

アレイのuniq

Posted feedbacks - Flatten