[cfoley]

Here is a java one that uses BitSets. O(max(lenA+lenB), maxVal)
It falls over if either of your lists contain negative numbers or Integer.MAX_VALUE. The latter is an easy fix but I lift it out for the sake of simplicity.

	static List<Integer> doppleganger(List<Integer> A, List<Integer> B)/> {
		BitSet bits = toBits(A);
		bits.and(toBits(B)/>);

		List<Integer> C = new ArrayList<Integer>();
		int i = -1;
		while ((i = bits.nextSetBit(i+1)) != -1) {
			C.add(i);
		}
		return C;
	}

	static BitSet toBits(List<Integer> L) {
		BitSet bits = new BitSet();
		for(int i : L) bits.set(i, true);
		return bits;
	}	

[m-e-g-a-z]

baavgai, on 27 July 2011 - 08:53 PM, said:

Hmm... what if the lists look like [ 2, 5, 5, 5, 8, 3, 3, 12 ], [ 12, 5, 5, 1, 3, 3, 3, 4 ].

The answer I'd want ( order doesn't matter): [3, 3, 12, 5, 5]

That's far more fun:

Spoiler

	public static ArrayList<Integer> intersection (ArrayList <Integer>x, ArrayList <Integer>y)
	{
		TreeMap <Integer,Integer> occurrence = new TreeMap <Integer,Integer>();
		ArrayList <Integer>list = new ArrayList<Integer>();
		for(Integer num: x){	
			if(!occurrence.containsKey(num))
			 occurrence.put(num, 1);
			else 
				occurrence.put(num, occurrence.get(num) + 1);
		}
	
		for(Integer num2: y){
			if (occurrence.containsKey(num2))
				occurrence.put(num2, occurrence.get(num2) + 1);
		}
		
		for(Map.Entry<Integer,Integer> submap : occurrence.entrySet()) {
		
			int value = submap.getValue()/2;
			while(value>0){
				list.add(submap.getKey());
				value--;
			}
		}
		
		return list;

[Nallo]

A rewrite of atraub's sorted list algorithm in haskell:

Spoiler

module Doppel
    (doppelganger)
    where

import List (sort)

addIfNeqHead :: Int -> [Int] -> [Int]
addIfNeqHead x []    = x:[]
addIfNeqHead x (h:t)
    | x == h         = h:t
    | otherwise      = x:h:t
     
doppelganger' :: [Int] -> [Int] -> [Int] -> [Int]
doppelganger' [] _   agg            = agg
doppelganger' _  []  agg            = agg 
doppelganger' (h1:t1) (h2:t2) agg
    | h1 < h2                       = doppelganger' t1 (h2:t2) agg
    | h1 > h2                       = doppelganger' (h1:t1) t2 agg
    | h1 == h2                      = doppelganger' t1 t2 (addIfNeqHead h1 agg)

doppelganger :: [Int] -> [Int] -> [Int]
doppelganger xs ys = doppelganger' (sort xs) (sort ys) []

[Curtis Rutland]

A rewrite of Nallo's rewrite of atraub's sorted list algorithm in F#:

Spoiler

let addIfNeqHead x lst = 
    match lst with
    | []                -> x::[]
    | h::t when x = h   -> h::t
    | h::t              -> x::h::t

let doppelganger x y =
    let rec doppelganger' xs ys agg = 
        match xs, ys with
        | [], _ -> agg
        | _, [] -> agg
        | h1::t1, h2::t2 ->
            match h1, h2 with
            | h1, h2 when h1 < h2   -> doppelganger' t1 (h2::t2) agg
            | h1, h2 when h1 > h2   -> doppelganger' (h1::t1) t2 agg
            | h1, h2                -> doppelganger' t1 t2 (addIfNeqHead h1 agg)
    doppelganger' (List.sort x) (List.sort y) []

Edit, this prints the matches in reverse order. If we want them ascending instead of descending, change this line:

//| h::t              -> x::h::t
  | h::t              -> h::t@x::[]

Example usage:

doppelganger [1; 2; 3; 4; 4; 5; 5;] [8; 2; 4; 3;] |> printfn "%A"
//include if running as console application
System.Console.ReadKey() |> ignore

Edit 2: I think I like this version better, it has less needless pattern matching, and I changed some naming up to make it more obvious to me:

Spoiler

let addIfNeqHead x agg = 
    match agg with
    | []              -> x::[]
    | h::t when x = h -> agg
    | _               -> x::agg

let intersect x y =
    let rec intersect x y agg = 
        match x, y with
        | [], _          -> agg
        | _, []          -> agg
        | xh::xt, yh::yt ->
            match xh, yh with
            | _ when xh < yh -> intersect xt y  agg
            | _ when xh > yh -> intersect x  yt agg
            | _              -> intersect xt yt (addIfNeqHead xh agg)
    intersect (List.sort x) (List.sort y) []

Example usage:

intersect [1; 2; 3; 4; 4; 5; 5;] [8; 2; 4; 3;] |> printfn "%A"
//include if running as console application
System.Console.ReadKey() |> ignore

This post has been edited by Curtis Rutland: 28 July 2011 - 12:04 PM

[Curtis Rutland]

Also, my version using a HashSet in F#:

Spoiler

open System.Collections.Generic
let intersection x y = 
    let hs = HashSet(x, HashIdentity.Structural)
    List.filter (fun i -> hs.Contains i) y

Edit: a shorter version using Set instead of HashSet

Spoiler

let intersect2 left right = List.filter (fun i -> set left |> Set.contains i) right

This post has been edited by Curtis Rutland: 28 July 2011 - 12:06 PM

[atraub]

haskell and f#.... wow guys...

[Nallo]

Quote

Any high level language will do fine... but no functional languages

I am sorry sir. I missed that order

[fromTheSprawl]

But isn't 5 always a 5? Then if you see a 5 in one set and two or three 5's in the other it would still need to show 5 since a doppelganger is a complete copy of something?

Or I'm just plain lazy. Here is the ugly code I made with PLSQL, hope to do baavgai's implementation in the future(more laziness!):

Spoiler

DECLARE
TYPE col is TABLE OF NUMBER;
set1 col;
set2 col;
resultSet col;
rs NUMBER;
BEGIN
set1:=col(3,8,9,3,1,4,9,9);
set2:=col(2,6,9,5,4,1,9);
rs:=1;
resultSet:=col(NULL);
FOR i in 1..set1.COUNT LOOP
	FOR g in 1..set2.COUNT LOOP
		IF set1(i) = set2(g) THEN
			IF resultSet.EXISTS(2) THEN
				FOR h in 1..resultSet.COUNT LOOP
					IF set1(i) = resultSet(h) AND h != resultSet.COUNT THEN
					EXIT;
					ELSIF set1(i) = resultSet(h) AND h = resultSet.COUNT THEN
					resultSet(rs):=set1(i);
					rs := rs + 1;
					resultSet.extend(1);
					EXIT;
					ELSIF  h = resultSet.COUNT THEN
					resultSet(rs):=set1(i);
					rs := rs + 1;
					resultSet.extend(1);
					END IF;
				END LOOP;
			ELSIF resultSet.COUNT = 1 THEN
					resultSet(rs):=set1(i);
					rs := rs + 1;
					resultSet.extend(1);
			END IF;
		END IF;
	END LOOP;
END LOOP;
for k in  1..resultSet.COUNT LOOP
DBMS_OUTPUT.PUT_LINE(resultSet(k));
END LOOP;
END;
/

OUTPUT:
9
1
4

Hid it in spoilers so as not to blind your eyes.

[Curtis Rutland]

atraub, on 28 July 2011 - 08:41 PM, said:

haskell and f#.... wow guys...

It's fun though. I mean, I could do that in Python or C#, but I'm trying to learn F#, so why not? I mean, sure, F# has a Sequence type with methods to do intersection automatically, but I'm actually implementing the filtering myself, without a set. Using the haskell version of your code, of course, but it's still fun.

Also, @Nallo,

atraub, on 27 July 2011 - 02:58 PM, said:

Fine, functional languages too

[anonymouscodder]

bash

Spoiler

function foo {
	echo `echo ${@}|tr " " "\n"|sort -n|uniq -d`
}
first=(1 2 4 5 6 8 10)
second=(1 3 5 7 9 10)
foo ${first[@]} ${second[@]}

This post has been edited by anonymouscodder: 28 July 2011 - 09:05 PM

[atraub]

haha I'm not judging, it's pretty hardcore that you guys want to do this in f#, haskell, and now bash!

[baavgai]

Well, to round it out...

I'll admit, I'm not real comfortable with functional languages. That is one of the many reasons I like Python; you can have fun with functional stuff without loosing your comfortable imperative home.

In Erlang, here's a one liner:

Spoiler

sets:to_list(sets:from_list([ X || X <- List1, lists:member(X, List2) ])).

However, it feels like it's cheating more than a little, because of the sets. Then again, sorting also feels like a cop out.

So, with no libraries at all ( I wrote my own lists:member equiv ), Erlang solution.

Spoiler

inlist([], _) -> false;
inlist([H|_], X) when X == H -> true;
inlist([_|T], X) -> inlist(T, X).

merge([], _) -> [];
merge([H|T], List2) -> 
	M = merge(T, List2), 
	InList = inlist(List2, H) and not inlist(M, H),
	if InList -> [H|M]; true -> M end.

There are probably a more clever ways to do that. I actually did a functional no no with anti tail end recursion, but it seems a reasonable solutions to me. The trick here is no built ins, which honestly make it too easy.

[atraub]

baavgai, on 29 July 2011 - 10:09 AM, said:

...sorting also feels like a cop out...

Harsh

[baavgai]

Lol!

atraub, on 27 July 2011 - 03:26 PM, said:

Haha don't be lame brewer! Create an actual algorithm for solving the problem

[ishkabible]

so i was reading Sergio Tapia's blog(here) about learning C Curt posted his F# snippet. i then translated it to Haskell which it had been translated from before. Curt pointed out that that bit of code went from Python->Haskell->F#->Haskell. so here is my bit of code.

Spoiler

addIfNeqHead x agg
    | null agg      = [x] 
    | x /= head agg = x : agg
    | otherwise     = agg

intersect' x y = intersect'' (sort x)  (sort y) []
    where intersect'' [] _ agg          = agg
          intersect'' _ [] agg          = agg
          intersect'' xn@(x:xs) yn@(y:ys) agg
              | x < y     = intersect'' xs yn agg
              | x > y     = intersect'' xn ys agg
              | otherwise = intersect'' xs ys (addIfNeqHead x agg)

oddly it got shorter with each translation

also for the hell of it here is one in Lua

Spoiler

function doppleganger(t1, t2)
	local record = {}
	local ret = {}
	for i=1, #t1, 1 do
		record[t1[i]] = true
	end
	for i=1, #t2, 1 do
		if record[t2[i]] then
			table.insert(ret, t2[i])
		end
	end
	return ret
end

This post has been edited by ishkabible: 29 July 2011 - 11:04 AM