Remove duplicate elements: Difference between revisions

 

There are basically three approaches seen here:

* Sort the elements and remove consecutive duplicate elements. The complexity of the best sorting algorithms is O(''n'' log ''n''). This approach requires that your type be "comparable", i.e., have an ordering. Putting the elements into a self-balancing binary search tree is a special case of sorting.

* Go through the list, and for each element, check the rest of the list to see if it appears again, and discard it if it does. The complexity is O(''n''²). The up-shot is that this always works on any type (provided that you can test for equality).

 

=={{header|ACL2}}==

 

 

begin

 

{{works with|Dyalog APL}}

The primitive monad ∪ means "unique", so:

 

{{works with|APL2}}

((⍳⍨w)=⍳⍴w)/w

 

=={{header|AppleScript}}==

 

on unique(x)

 

=={{header|AutoHotkey}}==

Built in Sort has an option to remove duplicates

Sort, a, a, NUD`,

 

=={{header|AWK}}==

 

{{works with|BBC BASIC for Windows}}

list$() = "Now", "is", "the", "time", "for", "all", "good", "men", \

\ "to", "come", "to", "the", "aid", "of", "the", "party."

IF j%>=i% l$(n%) = i$ : n% += 1

NEXT

<pre>

Now is the time for all good men to come aid of party.

</pre>

 

=={{header|Bracmat}}==

 

The list contains atoms and also a few non-atomic expressions. The hash table needs atomic keys, so we apply the <code>str</code> function when searching and inserting elements.

 

(A=

& !C

&

Only solution B produces a list with the same order of elements as in the input.

<pre>Solution A: 19 (4.4) 17 11 13 (1.1) (7.) 222 +11 7 5 3 2 0 cats (-100.2) +7

 

=={{header|Brat}}==

 

 

=={{header|C}}==

Since there's no way to know ahead of time how large the new data structure will need to be, we'll return a linked list instead of an array.

 

#include <stdlib.h>

 

printf("%d ", n->x);

puts("");

 

1 2 4 5 15 3

 

===O(n^2) version, pure arrays===

 

#include <stdlib.h>

#include <stdbool.h>

free(b);

return 0;

 

1 2 4 5 15 3

 

===Sorting method===

 

#include <stdlib.h>

 

 

return 0;

 

1

2

5

15

 

=={{header|C++}}==

This version uses <tt>std::set</tt>, which requires its element type be comparable using the < operator.

#include <iostream>

using namespace std;

cout << *iter << " ";

cout << endl;

 

This version uses <tt>hash_set</tt>, which is part of the SGI extension to the Standard Template Library. It is not part of the C++ standard library. It requires that its element type have a hash function.

 

{{works with|GCC}}

#include <iostream>

using namespace std;

cout << *iter << " ";

cout << endl;

 

This version uses <tt>unordered_set</tt>, which is part of the TR1, which is likely to be included in the next version of C++. It is not part of the C++ standard library. It requires that its element type have a hash function.

 

{{works with|GCC}}

#include <iostream>

using namespace std;

cout << *iter << " ";

cout << endl;

 

Alternative method working directly on the array:

 

#include <iterator>

#include <algorithm>

std::copy(data, new_end, std::ostream_iterator<int>(std::cout, " ");

std::cout << std::endl;

 

 

 

=={{header|Clojure}}==

 

(1 3 2 9 8 0)

 

=={{header|Common Lisp}}==

To remove duplicates non-destructively:

 

 

Or, to remove duplicates in-place:

 

 

=={{header|D}}==

 

<pre>[0, 1, 2, 3, 8, 9]</pre>

Using an associative array:

 

 

foreach (el; data)

<pre>[8, 0, 1, 9, 2, 3]</pre>

 

=={{header|Delphi}}==

Generics were added in Delphi2009.

 

 

{$APPTYPE CONSOLE}

lIntegerList.Free;

end;

 

<pre>1

2

4

5</pre>

 

=={{header|E}}==

 

 

=={{header|Erlang}}==

 

 

=={{header|Euphoria}}==

 

function uniq(sequence s)

constant s = {1, 2, 1, 4, 5, 2, 15, 1, 3, 4}

? s

 

<pre>{1,2,1,4,5,2,15,1,3,4}

{1,2,3,4,5,15}

=={{header|F Sharp|F#}}==

The simplest way is to build a set from the given array (this actually works for any enumerable input sequence type, not just arrays):

set [|1;2;3;2;3;4|]

gives:

val it : Set<int> = seq [1; 2; 3; 4]

 

=={{header|Factor}}==

 

 

 

=={{header|Forth}}==

The input data is assumed to be sorted.

 

\ a3 is the address beyond the data a2 is traversing.

: skip-dups ( a1 a2 a3 -- a1 a2+n )

cell+ r@ skip-dups

cell 0 d+ \ increment write ptr only

 

Here is another implementation of "uniq" that uses a popular parameters and local variables extension words. It is structurally the same as the above implementation, but uses less overt stack manipulation.

 

a n cells+ to e

a dup to r

cell+

repeat

 

To test this code, you can execute:

 

here test - cell / constant ntest

: .test ( n -- ) 0 ?do test i cells + ? loop ;

 

 

 

=={{header|Fortran}}==

Fortran has no built-in hash functions or sorting functions but the code below implements the compare all elements algorithm.

 

 

program remove_dups

end program remove_dups

 

 

=={{header|GAP}}==

a := [ 1, 2, 3, 1, [ 4 ], 5, 5, [4], 6 ];

# [ 1, 2, 3, 1, [ 4 ], 5, 5, [ 4 ], 6 ]

# true

IsList(b);

 

=={{header|Go}}==

import "fmt"

 

func uniq(list []int) []int {

}

 

func main() {

It takes only small changes to the above code to preserver order. Just store the sequence in the map:

 

import "fmt"

 

func uniq(list []int) []int {

}

 

func main() {

 

import (

)

 

func uniq(list []float64) []float64 {

}

 

func main() {

 

=={{header|Groovy}}==

assert list.size() == 12

 

list.unique()

assert list.size() == 8

 

 

// Converting to Set

assert set.size() == 8

 

 

=={{header|Haskell}}==

 

=={{header|HicEst}}==

CHARACTER :: workspace*100

 

READ(Text=workspace, ItemS=individuals) nums ! convert to numeric

 

 

=={{header|Icon}} and {{header|Unicon}}==

This solution preserves the original order of the elements.

every write(!noDups(args))

end

return a

}

A sample run is:

<pre>

=={{header|IDL}}==

 

 

=={{header|Inform 7}}==

 

let result be a list of Ks;

repeat with X running through L:

add X to result, if absent;

 

=={{header|J}}==

The verb<code> ~. </code>removes duplicate items from ''any'' array (numeric, character, or other; vector, matrix, rank-n array). For example:

4 3 2 8 0 1 9 5 7 6

~. 'chthonic eleemosynary paronomasiac'

 

0 0 0

0 1 2

0 0 0

0 1 2

 

=={{header|Java}}==

{{works with|Java|1.5}}

 

 

=={{header|JavaScript}}==

This uses the <code>===</code> "strict equality" operator, which does no type conversions (<code>4 == "4"</code> is true but <code>4 === "4"</code> is false)

// concat() with no args is a way to clone an array

var u = ary.concat().sort();

var uniq = unique(ary);

for (var i = 0; i < uniq.length; i++)

<pre>1 - number

2 - number

 

Or, extend the prototype for Array:

var u = this.concat().sort();

for (var i = 1; i < u.length; ) {

return u;

}

 

=={{header|Julia}}==

 

=={{header|K}}==

(Inspired by the J version.)

 

(12 7 12 4 3

6 3 7 4 7

(0 0 0

0 1 2

 

=={{header|Lang5}}==

 

: remove-duplicates

0 extract swap "2dup in if drop else append then" dip ;

 

Built-in function:

 

 

 

 

 

=={{header|Logo}}==

{{works with|UCB Logo}}

 

=={{header|Lua}}==

flags = {}

io.write('Unique items are:')

end

end

<pre>Unique items are: 1 2 3 4 bird cat dog</pre>

 

 

=={{header|Maple}}==

This is simplest with a list, which is an immutable array.

L := [1, 2, 1, 2, 3, 3, 2, 1, "a", "b", "b", "a", "c", "b"]

 

> [op]({op}(L));

That is idiomatic, but perhaps a bit cryptic; here is a more verbose equivalent:

For an Array, which is mutable, the table solution works well in Maple.

> for u in A do T[u] := 1 end: Array( [indices]( T, 'nolist' ) );

Note that the output (due to the Array() constructor) '''is''' in fact an Array.

 

Built-in function:

gives back:

 

=={{header|MATLAB}}==

MATLAB has a built-in function, "unique(list)", which performs this task.

<br \>Sample Usage:

 

ans =

 

 

NOTE: The unique function only works for vectors and not for true arrays.

=={{header|Maxima}}==

 

 

 

=={{header|MUMPS}}==

<p>We'll take advantage of the fact that an array can only have one index of any specific value. Sorting into canonical order is a side effect.

;L is the input listing

;S is the separator between entries

FOR SET I=$O(Z(I)) QUIT:I="" SET R=$SELECT($L(R)=0:I,1:R_S_I)

KILL Z,I

Example:<pre>USER>W $$REMDUPE^ROSETTA("1,2,3,4,5,2,5,""HELLO"",42,""WORLD""",",")

1,2,3,4,5,42,"HELLO","WORLD"</pre>

 

=={{header|Nemerle}}==

 

module RemDups

Main() : void

{

WriteLine(unique);

}

 

=={{header|NetRexx}}==

This sample takes advantage of the NetRexx built-in <tt>Rexx</tt> object's indexed string capability (associative arrays). <tt>Rexx</tt> indexed strings act very like hash tables:

options replace format comments java crossref symbols nobinary

 

 

return wordlist.space

<pre>

1: 2 3 5 7 11 13 17 19 cats 222 -100.2 11 1.1 7 7. 7 5 5 3 2 0 4.4 2

 

=={{header|NewLISP}}==

 

=={{header|Nial}}==

cull uniques

=+-+-+-+-+-+-+-+-+

=|1|2|3|a|b|c|4|d|

 

Using strand form

 

 

 

=={{header|Objeck}}==

use Structure;

 

}

}

 

=={{header|OCaml}}==

let unique_set = Hashtbl.create (List.length lst) in

 

let _ =

 

 

=={{header|Octave}}==

input=[1 2 6 4 2 32 5 5 4 3 3 5 1 2 32 4 4];

output=unique(input);

 

=={{header|ooRexx}}==

uniqueData = .set~new~union(data)~makearray~sort

 

do item over uniqueData

say item

 

=={{header|Oz}}==

The following solutions only works if the value type is allowed as a key in a dictionary.

 

 

fun {Nub Xs}

in

 

 

=={{header|PARI/GP}}==

Sort and remove duplicates. Other methods should be implemented as well.

vecsort(v,,8)

 

=={{header|Pascal}}==

 

const

for i := low(rArray) to last do

writeln (rArray[i]);

<pre>% ./RemoveDuplicates

1

{{libheader|List::MoreUtils}}

(this version even preserves the order of first appearance of each element)

 

 

It is implemented like this:

 

Note: the following two solutions convert elements to strings in the result, so if you give it references they will lose the ability to be dereferenced.

 

Alternately:

 

Alternately:

@seen{qw(1 2 3 a b c 2 3 4 b c d)} = ();

 

 

 

 

 

=={{header|PHP}}==

 

=={{header|PicoLisp}}==

There is a built-in function

<pre>-> (2 4 6 1 3 5)</pre>

 

=={{header|PL/I}}==

declare (i, j, k, n, e) fixed;

 

n = hbound(t,1);

i = 0;

 

put skip list ('Unique elements are:');

 

=={{header|Pop11}}==

 

lvars ar = {1 2 3 2 3 4};

;;; Create a hash table

;;; Collect keys into a list

lvars ls = [];