仲間はずれの判定 in Common Lisp DouKaku?

仲間はずれの判定

リストxsが渡されたときに

全部の要素が同じ値である(例：[1, 1, 1, 1])、
一つだけ仲間はずれがある(例：[1, 2, 1, 1, 1])、
その他

を識別する関数を作ってください。また判定後に「全部の要素が同じ値」の場合にはその値、「一つだけ仲間はずれがある」の場合にはその仲間はずれの値と多数派の値を複雑な処理なしに取得できるようにしてください。

型にうるさい言語のために：リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。

追記：リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。

もっとスリム化できそうですがとりあえず。

import java.util.*;
public class NakamaHazure {
    public static void main(String[] args) {
        check(Arrays.asList(1,1,1,1));    // => [1]
        check(Arrays.asList(1,2,1,1,1));    // => [2,1]
        check(Arrays.asList(1,2,2,1,1));    // => []
        check(Arrays.asList(1,2,2,1,3));    // => []
    }
    private static void check(List<Integer> list) {
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> minor = new HashSet<Integer>();;
        Integer major = null;
        for (Integer i : list) {
            if (!set.add(i)) {
                if (major != null && major != i) {
                    System.out.println("[]");
                    return;
                }
                minor.remove(i);
                major = i;
            } else {
                minor.add(i);
            }
        }
        if (set.size() == 1) {
            System.out.println("[" + set.iterator().next() + "]");
        } else if (set.size() == 2) {
            System.out.println("[" + minor.iterator().next() + "," + major + "]");
        } else {
            System.out.println("[]");
        }
    }
}

array_count_values便利ですね。あえて使わないで作ってみる事で便利さを際実感

$a[]= array(1,1,1,1);#1
$a[]= array(1,2,1,1,1);#2
$a[]= array(2,1,2,2);#その他
$a[]= array(1,2,2,2);#その他
$a[]= array(1,1,2,2);#その他
$a[]= array(1,1,2,3);#その他
function check($_array){
    $uniques = sizeof(array_unique($_array));
    switch($uniques){
        case(1):
            return array("仲間"=>array_pop($_array));
        case(2):
            sort($_array);
            #仲間はずれ
            if( $_array[0]!=$_array[1] ){
                return array( "仲間はずれ"=>array_shift($_array),"仲間"=>array_pop($_array) );
            }else if($_array[0]==$_array[1] && $_array[sizeof($_array)-1] != $_array[sizeof($_array)-2] ){
                return array( "仲間はずれ"=>array_pop($_array),"仲間"=>array_shift($_array) );
            }
        default:
            return "その他";
    }


}

foreach( $a as $b ){
    print_r( check($b) ).PHP_EOL;
}

post comment

Posted feedbacks - Common Lisp

再帰版。リストを先頭から見ていき、条件をみたさなくなったら即座に終了する。

(defun classify (list)
  (labels ((rec (list alist)
             (let ((pair (assoc (car list) alist))
                   (len (length alist)))
               (cond ((null list)
                      (if (= len 1)
                          (values :homo (caar alist))
                          (let ((one (position 1 (mapcar #'cdr alist))))
                            (case one
                              (0 (values :quasi-homo (caar alist) (caadr alist)))
                              (1 (values :quasi-homo (caadr alist) (caar alist)))
                              (t nil)))))
                     ((and (>= len 2) (null pair))
                      (return-from classify nil))
                     ((null pair)
                      (rec (cdr list) (cons (cons (car list) 1) alist)))
                     (t
                      (incf (cdr pair))
                      (rec (cdr list) alist))))))
    (rec list ())))
(multiple-value-list (classify '(1 1 1 1)))   ; => (:HOMO 1)
(multiple-value-list (classify '(1 2 1 1 1))) ; => (:QUASI-HOMO 2 1)
(multiple-value-list (classify '(1 1 1 1 2))) ; => (:QUASI-HOMO 2 1)
(multiple-value-list (classify '(2 2 1 1 1))) ; => (NIL)
(multiple-value-list (classify '(2 4 1 1 1))) ; => (NIL)
(multiple-value-list (classify '(1 2 3 4)))   ; => (NIL)
(multiple-value-list (classify '()))          ; => (NIL)

条件によって多値を返すようにしてみました。
* 全部の要素が同じ値である => 仲間, nil
* 一つだけ仲間はずれがある => 仲間はずれ, 仲間
* その他 => nil, もとのリスト

(defun hajiki (lst &optional &key (test #'equal))
  (let ((xs (remove (car lst) lst :test-not test))
	(ys (remove (car lst) lst :test test))
	(kind (let ((cnt 0) tem)
		(dolist (item lst cnt)
		  (or (eq tem (pushnew item tem :test test)) (incf cnt))
		  (and (> cnt 2) (return-from hajiki (values nil lst)))))))
    (if (= kind 1)
	(values (car xs) nil)
	(let ((xs-len (length xs))
	      (ys-len (length ys)))
	  (cond ((< xs-len ys-len ) (values (car xs) (car ys)))
		((= xs-len ys-len) (values nil lst))
		('T (values (car ys) (car xs))))))))

コメントありがとうございます!
全然気付きませんでした^^;
返す値にタグを付けて区別するようにしてみました。
それとひとりぼっちを選択するのではなく、
少ない方選択していたバグがあったので直しました。

(defun hajiki (lst &optional &key (test #'equal))
  (let ((xs (remove (car lst) lst :test-not test))
	(ys (remove (car lst) lst :test test))
	(kind (let ((cnt 0) tem)
		(dolist (item lst cnt)
		  (or (eq tem (pushnew item tem :test test)) (incf cnt))
		  (and (> cnt 2) (return-from hajiki (values nil lst :hetero)))))))
    (if (<= kind 1)
	(values (car xs) nil :homo)
	(let ((xs-len (length xs))
	      (ys-len (length ys)))
	  (if (and (= (min xs-len ys-len) 1) (not (= xs-len ys-len 1)))
	      (if (< xs-len ys-len)
		  (values (car xs) (car ys) :hetero)
		  (values (car ys) (car xs) :hetero))
	      (values nil lst :hetero))))))

DouKaku?

仲間はずれの判定

Posted feedbacks - Common Lisp

Index

Feed

Other

Link

Pathtraq