Remove duplicate elements
Given an Array, derive a sequence of elements in which all duplicates are removed.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
There are basically three approaches seen here:
- Put the elements into a hash table which does not allow duplicates. The complexity is O(n) on average, and O(n2) worst case. This approach requires a hash function for your type (which is compatible with equality), either built-in to your language, or provided by the user.
- 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(n2). The up-shot is that this always works on any type (provided that you can test for equality).
ACL2
<lang lisp>(remove-duplicates xs)</lang>
Applesoft BASIC
<lang basic>100 DIM L$(15) 110 L$(0) = "NOW" 120 L$(1) = "IS" 130 L$(2) = "THE" 140 L$(3) = "TIME" 150 L$(4) = "FOR" 160 L$(5) = "ALL" 170 L$(6) = "GOOD" 180 L$(7) = "MEN" 190 L$(8) = "TO" 200 L$(9) = "COME" 210 L$(10) = "TO" 220 L$(11) = "THE" 230 L$(12) = "AID" 240 L$(13) = "OF" 250 L$(14) = "THE" 260 L$(15) = "PARTY."
300 N = 15 310 GOSUB 400 320 FOR I = 0 TO N 330 PRINT L$(I) " " ; 340 NEXT 350 PRINT 360 END
400 REMREMOVE DUPLICATES 410 FOR I = N TO 1 STEP -1 420 I$ = L$(I) 430 FOR J = 0 TO I - 1 440 EQ = I$ = L$(J) 450 IF NOT EQ THEN NEXT J 460 IF EQ THEN GOSUB 500 470 NEXT I 480 RETURN
500 REMREMOVE ELEMENT 510 L$(I) = L$(N) 520 L$(N) = "" 530 N = N - 1 540 RETURN</lang>
Ada
<lang ada>with Ada.Containers.Ordered_Sets; with Ada.Text_IO; use Ada.Text_IO;
procedure Unique_Set is
package Int_Sets is new Ada.Containers.Ordered_Sets(Integer); use Int_Sets; Nums : array (Natural range <>) of Integer := (1,2,3,4,5,5,6,7,1); Unique : Set; Set_Cur : Cursor; Success : Boolean;
begin
for I in Nums'range loop Unique.Insert(Nums(I), Set_Cur, Success); end loop; Set_Cur := Unique.First; loop Put_Line(Item => Integer'Image(Element(Set_Cur))); exit when Set_Cur = Unique.Last; Set_Cur := Next(Set_Cur); end loop;
end Unique_Set;</lang>
APL
The primitive monad ∪ means "unique", so: <lang apl>∪ 1 2 3 1 2 3 4 1 1 2 3 4</lang>
<lang apl>w←1 2 3 1 2 3 4 1
((⍳⍨w)=⍳⍴w)/w
1 2 3 4</lang>
AppleScript
<lang applescript>unique({1, 2, 3, "a", "b", "c", 2, 3, 4, "b", "c", "d"})
on unique(x) set R to {} repeat with i in x if i is not in R then set end of R to i's contents end repeat return R end unique</lang>
AutoHotkey
Built in Sort has an option to remove duplicates <lang AutoHotkey>a = 1,2,1,4,5,2,15,1,3,4 Sort, a, a, NUD`, MsgBox % a ; 1,2,3,4,5,15</lang>
AWK
We produce an array a with duplicates from a string; then index a second array b with the contents of a, so that duplicates make only one entry; then produce a string with the keys of b, which is finally output. <lang awk>$ awk 'BEGIN{split("a b c d c b a",a);for(i in a)b[a[i]]=1;r="";for(i in b)r=r" "i;print r}' a b c d</lang>
BBC BASIC
<lang bbcbasic> DIM list$(15)
list$() = "Now", "is", "the", "time", "for", "all", "good", "men", \ \ "to", "come", "to", "the", "aid", "of", "the", "party." num% = FNremoveduplicates(list$()) FOR i% = 0 TO num%-1 PRINT list$(i%) " " ; NEXT PRINT END DEF FNremoveduplicates(l$()) LOCAL i%, j%, n%, i$ n% = 1 FOR i% = 1 TO DIM(l$(), 1) i$ = l$(i%) FOR j% = 0 TO i%-1 IF i$ = l$(j%) EXIT FOR NEXT IF j%>=i% l$(n%) = i$ : n% += 1 NEXT = n%</lang>
Output:
Now is the time for all good men to come aid of party.
Bracmat
Here are three solutions. The first one (A) uses a hash table, the second (B) uses a pattern for spotting the elements that have a copy further on in the list and only adds those elements to the answer that don't have copies further on. The third solution (C) utilises an mechanism that is very typical of Bracmat, namely that sums (and also products) always are transformed to a normalised form upon evaluation. Normalisation means that terms are ordered in a unique way and that terms that are equal, apart from a numerical factor, are replaced by a single term with a numerical factor that is the sum of the numerical factors of each term. The answer is obtained by replacing all numerical factors by 1
as the last step.
The list contains atoms and also a few non-atomic expressions. The hash table needs atomic keys, so we apply the str
function when searching and inserting elements.
<lang bracmat>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:?LIST
(A=
( Hashing = h elm list . new$hash:?h & whl ' ( !arg:%?elm ?arg & ( (h..find)$str$!elm | (h..insert)$(str$!elm.!elm) ) ) & :?list & (h..forall) $ ( = .!arg:(?.?arg)&!arg !list:?list ) & !list )
& put$("Solution A:" Hashing$!LIST \n,LIN) );
(B=
( backtracking = answr elm . :?answr & !arg : ? ( %?`elm ? ( !elm ? | &!answr !elm:?answr ) & ~ ) | !answr )
& put$("Solution B:" backtracking$!LIST \n,LIN) );
(C=
( summing = sum car LIST . !arg:?LIST & 0:?sum & whl ' ( !LIST:%?car ?LIST & (.!car)+!sum:?sum ) & whl ' ( !sum:#*(.?el)+?sum & !el !LIST:?LIST ) & !LIST )
& put$("Solution C:" summing$!LIST \n,LIN) );
( !A & !B & !C & )</lang> Only solution B produces a list with the same order of elements as in the input.
Solution A: 19 (4.4) 17 11 13 (1.1) (7.) 222 +11 7 5 3 2 0 cats (-100.2) +7 Solution B: 11 13 17 19 cats 222 (-100.2) +11 (1.1) +7 (7.) 7 5 3 0 (4.4) 2 Solution C: (7.) (4.4) (1.1) (-100.2) cats 222 19 17 13 11 7 5 3 2 0 +7 +11
Brat
<lang brat>some_array = [1 1 2 1 'redundant' [1 2 3] [1 2 3] 'redundant']
unique_array = some_array.unique</lang>
C
O(n^2) version, using linked lists
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.
<lang c>#include <stdio.h>
- include <stdlib.h>
struct list_node {int x; struct list_node *next;}; typedef struct list_node node;
node * uniq(int *a, unsigned alen)
{if (alen == 0) return NULL; node *start = malloc(sizeof(node)); if (start == NULL) exit(EXIT_FAILURE); start->x = a[0]; start->next = NULL;
for (int i = 1 ; i < alen ; ++i) {node *n = start; for (;; n = n->next) {if (a[i] == n->x) break; if (n->next == NULL) {n->next = malloc(sizeof(node)); n = n->next; if (n == NULL) exit(EXIT_FAILURE); n->x = a[i]; n->next = NULL; break;}}}
return start;}
int main(void)
{int a[] = {1, 2, 1, 4, 5, 2, 15, 1, 3, 4}; for (node *n = uniq(a, 10) ; n != NULL ; n = n->next) printf("%d ", n->x); puts(""); return 0;}</lang>
Output:
1 2 4 5 15 3
O(n^2) version, pure arrays
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <stdbool.h>
- include <string.h>
/* Returns `true' if element `e' is in array `a'. Otherwise, returns `false'.
* Checks only the first `n' elements. Pure, O(n). */
bool elem(int *a, size_t n, int e) {
for (size_t i = 0; i < n; ++i) if (a[i] == e) return true;
return false;
}
/* Removes the duplicates in array `a' of given length `n'. Returns the number
* of unique elements. In-place, order preserving, O(n ^ 2). */
size_t nub(int *a, size_t n) {
size_t m = 0;
for (size_t i = 0; i < n; ++i) if (!elem(a, m, a[i])) a[m++] = a[i];
return m;
}
/* Out-place version of `nub'. Pure, order preserving, alloc < n * sizeof(int)
* bytes, O(n ^ 2). */
size_t nub_new(int **b, int *a, size_t n) {
int *c = malloc(n * sizeof(int)); memcpy(c, a, n * sizeof(int)); int m = nub(c, n); *b = malloc(m * sizeof(int)); memcpy(*b, c, m * sizeof(int)); free(c); return m;
}
int main(void) {
int a[] = {1, 2, 1, 4, 5, 2, 15, 1, 3, 4}; int *b;
size_t n = nub_new(&b, a, sizeof(a) / sizeof(a[0]));
for (size_t i = 0; i < n; ++i) printf("%d ", b[i]); puts("");
free(b); return 0;
}</lang>
Output:
1 2 4 5 15 3
Sorting method
Using qsort and return uniques in-place:<lang c>#include <stdio.h>
- include <stdlib.h>
int icmp(const void *a, const void *b) {
- define _I(x) *(const int*)x
return _I(a) < _I(b) ? -1 : _I(a) > _I(b);
- undef _I
}
/* filter items in place and return number of uniques. if a separate
list is desired, duplicate it before calling this function */
int uniq(int *a, int len) { int i, j; qsort(a, len, sizeof(int), icmp); for (i = j = 0; i < len; i++) if (a[i] != a[j]) a[++j] = a[i]; return j + 1; }
int main() { int x[] = {1, 2, 1, 4, 5, 2, 15, 1, 3, 4}; int i, len = uniq(x, sizeof(x) / sizeof(x[0])); for (i = 0; i < len; i++) printf("%d\n", x[i]);
return 0; }</lang>
Output:
1 2 3 4 5 15
C++
This version uses std::set, which requires its element type be comparable using the < operator. <lang cpp>#include <set>
- include <iostream>
using namespace std;
int main() {
typedef set<int> TySet; int data[] = {1, 2, 3, 2, 3, 4};
TySet unique_set(data, data + 6);
cout << "Set items:" << endl; for (TySet::iterator iter = unique_set.begin(); iter != unique_set.end(); iter++) cout << *iter << " "; cout << endl;
}</lang>
This version uses hash_set, 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.
<lang cpp>#include <ext/hash_set>
- include <iostream>
using namespace std;
int main() {
typedef __gnu_cxx::hash_set<int> TyHash; int data[] = {1, 2, 3, 2, 3, 4};
TyHash unique_set(data, data + 6);
cout << "Set items:" << endl; for (TyHash::iterator iter = unique_set.begin(); iter != unique_set.end(); iter++) cout << *iter << " "; cout << endl;
}</lang>
This version uses unordered_set, 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.
<lang cpp>#include <tr1/unordered_set>
- include <iostream>
using namespace std;
int main() {
typedef tr1::unordered_set<int> TyHash; int data[] = {1, 2, 3, 2, 3, 4};
TyHash unique_set(data, data + 6);
cout << "Set items:" << endl; for (TyHash::iterator iter = unique_set.begin(); iter != unique_set.end(); iter++) cout << *iter << " "; cout << endl;
}</lang>
Alternative method working directly on the array:
<lang cpp>#include <iostream>
- include <iterator>
- include <algorithm>
// helper template template<typename T> T* end(T (&array)[size]) { return array+size; }
int main() {
int data[] = { 1, 2, 3, 2, 3, 4 }; std::sort(data, end(data)); int* new_end = std::unique(data, end(data)); std::copy(data, new_end, std::ostream_iterator<int>(std::cout, " "); std::cout << std::endl;
}</lang>
Using sort, unique, and erase on a vector.
<lang cpp>#include <algorithm>
- include <iostream>
- include <vector>
int main() {
std::vector<int> data = {1, 2, 3, 2, 3, 4};
std::sort(data.begin(), data.end()); data.erase(std::unique(data.begin(), data.end()), data.end());
for(int& i: data) std::cout << i << " "; std::cout << std::endl; return 0;
}</lang>
C#
<lang csharp>int[] nums = { 1, 1, 2, 3, 4, 4 }; List<int> unique = new List<int>(); foreach (int n in nums)
if (!unique.Contains(n)) unique.Add(n);</lang>
<lang csharp>int[] nums = {1, 1, 2, 3, 4, 4}; int[] unique = nums.Distinct().ToArray();</lang>
CafeOBJ
<lang CafeOBJ> -- The parametrized module NO-DUP-LIST(ELEMENTS :: TRIV) defines the signature of simple Haskell like list structure. -- The removal of duplicates is handled by the equational properties listed after the signature in brackets {} -- The binary operation _,_ is associative, commutative, and idempotent. -- This list structure does not permit duplicates, they are removed during evaluation (called reduction in CafeOBJ) -- Actual code is contained in module called NO-DUP-LIST. -- The tests are performed after opening instantiated NO-DUP-LIST with various concrete types. -- For further details see: http://www.ldl.jaist.ac.jp/cafeobj/ mod! NO-DUP-LIST(ELEMENTS :: TRIV) {
[ List < Elem < Elt] -- Sorts in Ordered Sorted Algebra op [] : -> List { prec: 0 } -- Empty List op _,_ : Elt Elt -> Elt { comm assoc idem prec: 80 l-assoc } op [_] : Elt -> List { prec: 0 }
}
-- Test on lists of INT, CHARACTER, and STRING open NO-DUP-LIST(INT) reduce [ 1 , 2 , 1 , 1 ] . -- Gives [ 1 , 2 ] open NO-DUP-LIST(CHARACTER) reduce [ 'a' , 'b' , 'a' , 'a' ] . -- Gives [ 'a' , 'b' ] open NO-DUP-LIST(STRING) reduce [ "abc" , "def" , "abc" ] . -- Gives [ "def" , "abc" ] </lang>
Clojure
<lang lisp>user=> (distinct [1 3 2 9 1 2 3 8 8 1 0 2]) (1 3 2 9 8 0) user=></lang>
Common Lisp
To remove duplicates non-destructively:
<lang lisp>(remove-duplicates '(1 3 2 9 1 2 3 8 8 1 0 2)) > (9 3 8 1 0 2)</lang>
Or, to remove duplicates in-place:
<lang lisp>(delete-duplicates '(1 3 2 9 1 2 3 8 8 1 0 2)) > (9 3 8 1 0 2)</lang>
D
<lang d>void main() {
import std.stdio, std.algorithm;
[1, 3, 2, 9, 1, 2, 3, 8, 8, 1, 0, 2] .sort() .uniq .writeln;
}</lang>
- Output:
[0, 1, 2, 3, 8, 9]
Using an associative array: <lang d>void main() {
import std.stdio;
immutable data = [1, 3, 2, 9, 1, 2, 3, 8, 8, 1, 0, 2];
bool[int] hash; foreach (el; data) hash[el] = true; hash.byKey.writeln;
}</lang>
- Output:
[8, 0, 1, 9, 2, 3]
Delphi
Generics were added in Delphi2009.
<lang Delphi>program RemoveDuplicateElements;
{$APPTYPE CONSOLE}
uses Generics.Collections;
var
i: Integer; lIntegerList: TList<Integer>;
const
INT_ARRAY: array[1..7] of Integer = (1, 2, 2, 3, 4, 5, 5);
begin
lIntegerList := TList<Integer>.Create; try for i in INT_ARRAY do if not lIntegerList.Contains(i) then lIntegerList.Add(i);
for i in lIntegerList do Writeln(i); finally lIntegerList.Free; end;
end.</lang>
Output:
1 2 3 4 5
Déjà Vu
<lang dejavu>} for item in [ 1 10 1 :hi :hello :hi :hi ]: @item !. keys set{</lang>
- Output:
[ 1 :hello 10 :hi ]
E
<lang e>[1,2,3,2,3,4].asSet().getElements()</lang>
ECL
<lang ecl> inNumbers := DATASET([{1},{2},{3},{4},{1},{1},{7},{8},{9},{9},{0},{0},{3},{3},{3},{3},{3}], {INTEGER Field1}); DEDUP(SORT(inNumbers,Field1)); </lang> Output:
0 1 2 3 4 7 8 9
Erlang
<lang erlang>List = [1, 2, 3, 2, 2, 4, 5, 5, 4, 6, 6, 5]. UniqueList = gb_sets:to_list(gb_sets:from_list(List)). % Alternatively the builtin: Unique_list = lists:usort( List ). </lang>
Euphoria
<lang euphoria>include sort.e
function uniq(sequence s)
sequence out s = sort(s) out = s[1..1] for i = 2 to length(s) do if not equal(s[i],out[$]) then out = append(out, s[i]) end if end for return out
end function
constant s = {1, 2, 1, 4, 5, 2, 15, 1, 3, 4} ? s ? uniq(s)</lang>
Output:
{1,2,1,4,5,2,15,1,3,4} {1,2,3,4,5,15}
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): <lang fsharp> set [|1;2;3;2;3;4|] </lang> gives: <lang fsharp> val it : Set<int> = seq [1; 2; 3; 4] </lang>
Factor
<lang factor>USING: sets ; V{ 1 2 1 3 2 4 5 } members .
V{ 1 2 3 4 5 }</lang>
Forth
Forth has no built-in hashtable facility, so the easiest way to achieve this goal is to take the "uniq" program as an example.
The word uniq, if given a sorted array of cells, will remove the duplicate entries and return the new length of the array. For simplicity, uniq has been written to process cells (which are to Forth what "int" is to C), but could easily be modified to handle a variety of data types through deferred procedures, etc.
The input data is assumed to be sorted.
<lang forth>\ Increments a2 until it no longer points to the same value as a1 \ a3 is the address beyond the data a2 is traversing.
- skip-dups ( a1 a2 a3 -- a1 a2+n )
dup rot ?do over @ i @ <> if drop i leave then cell +loop ;
\ Compress an array of cells by removing adjacent duplicates \ Returns the new count
- uniq ( a n -- n2 )
over >r \ Original addr to return stack cells over + >r \ "to" addr now on return stack, available as r@ dup begin ( write read ) dup r@ < while 2dup @ swap ! \ copy one cell cell+ r@ skip-dups cell 0 d+ \ increment write ptr only repeat r> 2drop r> - cell / ;</lang>
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.
<lang forth>: uniqv { a n \ r e -- n }
a n cells+ to e a dup to r \ the write address lives on the stack begin r e < while r @ over ! r cell+ e skip-dups to r cell+ repeat a - cell / ;</lang>
To test this code, you can execute:
<lang forth>create test 1 , 2 , 3 , 2 , 6 , 4 , 5 , 3 , 6 , here test - cell / constant ntest
- .test ( n -- ) 0 ?do test i cells + ? loop ;
test ntest 2dup cell-sort uniq .test</lang>
output
<lang forth>1 2 3 4 5 6 ok</lang>
Fortran
Fortran has no built-in hash functions or sorting functions but the code below implements the compare all elements algorithm.
<lang fortran>
program remove_dups
implicit none integer :: example(12) ! The input integer :: res(size(example)) ! The output integer :: k ! The number of unique elements integer :: i, j
example = [1, 2, 3, 2, 2, 4, 5, 5, 4, 6, 6, 5] k = 1 res(1) = example(1) outer: do i=2,size(example) do j=1,k if (res(j) == example(i)) then ! Found a match so start looking again cycle outer end if end do ! No match found so add it to the output k = k + 1 res(k) = example(i) end do outer write(*,advance='no',fmt='(a,i0,a)') 'Unique list has ',k,' elements: ' write(*,*) res(1:k)
end program remove_dups
</lang>
Frink
The following demonstrates two of the simplest ways of removing duplicates. <lang frink> b = [1, 5, 2, 6, 6, 2, 2, 1, 9, 8, 6, 5]
// One way, using OrderedList. An OrderedList is a type of array that keeps // its elements in order. The items must be comparable. a = new OrderedList println[a.insertAllUnique[b]]
// Another way, using the "set" datatype and back to an array. println[toArray[toSet[b]] </lang>
Output. Note that sets are not guaranteed to be printed in any specific order.
[1, 2, 5, 6, 8, 9] [9, 8, 6, 5, 2, 1]
GAP
<lang gap># Built-in, using sets (which are also lists) a := [ 1, 2, 3, 1, [ 4 ], 5, 5, [4], 6 ];
- [ 1, 2, 3, 1, [ 4 ], 5, 5, [ 4 ], 6 ]
b := Set(a);
- [ 1, 2, 3, 5, 6, [ 4 ] ]
IsSet(b);
- true
IsList(b);
- true</lang>
Go
- Map solution
<lang go>package main import "fmt"
func uniq(list []int) []int {
unique_set := make(map[int] bool, len(list)) for _, x := range list { unique_set[x] = true } result := make([]int, len(unique_set)) i := 0 for x := range unique_set { result[i] = x i++ } return result
}
func main() {
fmt.Println(uniq([]int {1,2,3,2,3,4})) // prints: [3 1 4 2]
}</lang>
- Map preserving order
It takes only small changes to the above code to preserver order. Just store the sequence in the map: <lang go>package main
import "fmt"
func uniq(list []int) []int {
unique_set := make(map[int]int, len(list)) i := 0 for _, x := range list { if _, there := unique_set[x]; !there { unique_set[x] = i i++ } } result := make([]int, len(unique_set)) for x, i := range unique_set { result[i] = x } return result
}
func main() {
fmt.Println(uniq([]int{1, 2, 3, 2, 3, 4})) // prints: [1 2 3 4]
}</lang>
- Float64, removing duplicate NaNs.
In solutions above, you just replace "int" with another type to use for a list of another type. (See Associative_arrays/Creation#Go for acceptable types.) Except a weird thing happens with NaNs. They don't compare equal, so you have to special case them if you want to remove duplicates: <lang go>package main
import (
"fmt" "math"
)
func uniq(list []float64) []float64 {
unique_set := map[float64]int{} i := 0 nan := false for _, x := range list { if _, exists := unique_set[x]; exists { continue } if math.IsNaN(x) { if nan { continue } else { nan = true } } unique_set[x] = i i++ } result := make([]float64, len(unique_set)) for x, i := range unique_set { result[i] = x } return result
}
func main() {
fmt.Println(uniq([]float64{1, 2, math.NaN(), 2, math.NaN(), 4}))
}</lang>
Groovy
<lang groovy>def list = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'] assert list.size() == 12 println " Original List: ${list}"
// Filtering the List list.unique() assert list.size() == 8 println " Filtered List: ${list}"
list = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'] assert list.size() == 12
// Converting to Set def set = new HashSet(list) assert set.size() == 8 println " Set: ${set}"
// Converting to Order-preserving Set set = new LinkedHashSet(list) assert set.size() == 8 println "List-ordered Set: ${set}"</lang>
Output:
Original List: [1, 2, 3, a, b, c, 2, 3, 4, b, c, d] Filtered List: [1, 2, 3, a, b, c, 4, d] Set: [1, d, 2, 3, 4, b, c, a] List-ordered Set: [1, 2, 3, a, b, c, 4, d]
Haskell
<lang haskell>values = [1,2,3,2,3,4] unique = List.nub values</lang>
HicEst
<lang hicest>REAL :: nums(12) CHARACTER :: workspace*100
nums = (1, 3, 2, 9, 1, 2, 3, 8, 8, 1, 0, 2) WRITE(Text=workspace) nums ! convert to string EDIT(Text=workspace, SortDelDbls=workspace) ! do the job for a string READ(Text=workspace, ItemS=individuals) nums ! convert to numeric
WRITE(ClipBoard) individuals, "individuals: ", nums ! 6 individuals: 0 1 2 3 8 9 0 0 0 0 0 0 </lang>
Icon and Unicon
This solution preserves the original order of the elements. <lang Icon>procedure main(args)
every write(!noDups(args))
end
procedure noDups(L)
every put(newL := [], notDup(set(),!L)) return newL
end
procedure notDup(cache, a)
if not member(cache, a) then { insert(cache, a) return a }
end</lang> A sample run is:
->noDups a b c d c a b e a b c d e ->
IDL
<lang idl>non_repeated_values = array[uniq(array, sort( array))]</lang>
Inform 7
<lang inform7>To decide which list of Ks is (L - list of values of kind K) without duplicates: let result be a list of Ks; repeat with X running through L: add X to result, if absent; decide on result.</lang>
J
The verb ~.
removes duplicate items from any array (numeric, character, or other; vector, matrix, rank-n array). For example:
<lang j> ~. 4 3 2 8 0 1 9 5 1 7 6 3 9 9 4 2 1 5 3 2
4 3 2 8 0 1 9 5 7 6
~. 'chthonic eleemosynary paronomasiac'
chtoni elmsyarp</lang> Or
<lang j> 0 1 1 2 0 */0 1 2 0 0 0 0 1 2 0 1 2 0 2 4 0 0 0
~. 0 1 1 2 0 */0 1 2
0 0 0 0 1 2 0 2 4</lang>
Java
<lang java5>import java.util.Set; import java.util.HashSet; import java.util.Arrays;
Object[] data = {1, 2, 3, "a", "b", "c", 2, 3, 4, "b", "c", "d"}; Set<Object> uniqueSet = new HashSet<Object>(Arrays.asList(data)); Object[] unique = uniqueSet.toArray();</lang>
JavaScript
This uses the ===
"strict equality" operator, which does no type conversions (4 == "4"
is true but 4 === "4"
is false)
<lang javascript>function unique(ary) {
// concat() with no args is a way to clone an array var u = ary.concat().sort(); for (var i = 1; i < u.length; ) { if (u[i-1] === u[i]) u.splice(i,1); else i++; } return u;
}
var ary = [1, 2, 3, "a", "b", "c", 2, 3, 4, "b", "c", "d", "4"]; var uniq = unique(ary); for (var i = 0; i < uniq.length; i++)
print(uniq[i] + "\t" + typeof(uniq[i]));</lang>
1 - number 2 - number 3 - number 4 - number 4 - string a - string b - string c - string d - string
Or, extend the prototype for Array: <lang javascript>Array.prototype.unique = function() {
var u = this.concat().sort(); for (var i = 1; i < u.length; ) { if (u[i-1] === u[i]) u.splice(i,1); else i++; } return u;
} var uniq = [1, 2, 3, "a", "b", "c", 2, 3, 4, "b", "c", "d"].unique();</lang>
jq
If it is acceptable to alter the ordering of elements, then the builtin (fast) filter, *unique/0*, can be used. It returns the elements in sorted order. <lang jq>[4,3,2,1,1,2,3,4] | unique</lang>
If all but the first occurrence of each element should be deleted, then the following function could be used, at least in a pinch: <lang jq>def removeAllButFirst:
unique as $u | reduce .[] as $i # [ answer, $u ] ([ [], $u ]; (.[1]|index($i)) as $ix | if $ix then [ (.[0] + [$i]), (.[1]|delpaths($ix) ) ] else . end) | .[0] ;
</lang>
Julia
<lang julia>a = [1,2,3,4,1,2,3,4] unique(a)</lang>
K
(Inspired by the J version.)
<lang K> a:4 5#20?13 / create a random 4 x 5 matrix (12 7 12 4 3
6 3 7 4 7 3 8 3 1 2 2 12 6 4 1)
,/a / flatten to array
12 7 12 4 3 6 3 7 4 7 3 8 3 1 2 2 12 6 4 1
?,/a / distinct elements
12 7 4 3 6 8 1 2
?"chthonic eleemosynary paronomasiac"
"chtoni elmsyarp"
?("this";"that";"was";"that";"was";"this")
("this"
"that" "was") 0 1 1 2 0 *\: 0 1 2
(0 0 0
0 1 2 0 1 2 0 2 4 0 0 0)
?0 1 1 2 0 *\: 0 1 2
(0 0 0
0 1 2 0 2 4)</lang>
Lang5
<lang lang5>: dip swap '_ set execute _ ;
- remove-duplicates
[] swap do unique? length 0 == if break then loop drop ;
- unique?
0 extract swap "2dup in if drop else append then" dip ;
[1 2 6 3 6 4 5 6] remove-duplicates .</lang> Built-in function: <lang lang5>[1 2 6 3 6 4 5 6] 's distinct [1 2 6 3 6 4 5 6] 's dress dup union .</lang>
Lasso
<lang Lasso >local( x = array(3,4,8,1,8,1,4,5,6,8,9,6), y = array ) with n in #x where #y !>> #n do => { #y->insert(#n) } // result: array(3, 4, 8, 1, 5, 6, 9)</lang>
Liberty BASIC
LB has arrays, but here the elements are stored in a space-separated string. <lang lb> a$ =" 1 $23.19 2 elbow 3 2 Bork 4 3 elbow 2 $23.19 " print "Original set of elements = ["; a$; "]"
b$ =removeDuplicates$( a$) print "With duplicates removed = ["; b$; "]"
end
function removeDuplicates$( in$)
o$ =" " i =1 do term$ =word$( in$, i, " ") if instr( o$, " "; term$; " ") =0 and term$ <>" " then o$ =o$ +term$ +" " i =i +1 loop until term$ ="" removeDuplicates$ =o$
end function </lang>
Original set of elements = [ 1 $23.19 2 elbow 3 2 Bork 4 3 elbow 2 $23.19 ] With duplicates removed = [ 1 $23.19 2 elbow 3 Bork 4 ]
Logo
<lang logo>show remdup [1 2 3 a b c 2 3 4 b c d] ; [1 a 2 3 4 b c d]</lang>
Lua
<lang Lua>items = {1,2,3,4,1,2,3,4,"bird","cat","dog","dog","bird"} flags = {} io.write('Unique items are:') for i=1,#items do
if not flags[items[i]] then io.write(' ' .. items[i]) flags[items[i]] = true end
end io.write('\n')</lang> Output:
Unique items are: 1 2 3 4 bird cat dog
MAXScript
<lang maxscript>uniques = #(1, 2, 3, "a", "b", "c", 2, 3, 4, "b", "c", "d") for i in uniques.count to 1 by -1 do (
id = findItem uniques uniques[i] if (id != i) do deleteItem uniques i
)</lang>
Maple
This is simplest with a list, which is an immutable array. <lang Maple>> L := [ 1, 2, 1, 2, 3, 3, 2, 1, "a", "b", "b", "a", "c", "b" ];
L := [1, 2, 1, 2, 3, 3, 2, 1, "a", "b", "b", "a", "c", "b"]
> [op]({op}(L));
[1, 2, 3, "a", "b", "c"]</lang>
That is idiomatic, but perhaps a bit cryptic; here is a more verbose equivalent: <lang Maple>> convert( convert( L, 'set' ), 'list' );
[1, 2, 3, "a", "b", "c"]</lang>
For an Array, which is mutable, the table solution works well in Maple. <lang Maple>> A := Array( L ): > for u in A do T[u] := 1 end: Array( [indices]( T, 'nolist' ) );
[1, 2, 3, "c", "a", "b"]</lang>
Note that the output (due to the Array() constructor) is in fact an Array.
Mathematica
Built-in function: <lang Mathematica>DeleteDuplicates[{0, 2, 1, 4, 2, 0, 3, 1, 1, 1, 0, 3}]</lang> gives back: <lang Mathematica>{0, 2, 1, 4, 3}</lang> Custom function (reordering of elements is possible): <lang Mathematica>NoDupes[input_List] := Split[Sort[input]]All, 1 NoDupes[{0, 2, 1, 4, 2, 0, 3, 1, 1, 1, 0, 3}]</lang> gives back: <lang Mathematica>{0, 1, 2, 3, 4}</lang>
MATLAB
MATLAB has a built-in function, "unique(list)", which performs this task.
Sample Usage:
<lang MATLAB>>> unique([1 2 6 3 6 4 5 6])
ans =
1 2 3 4 5 6</lang>
NOTE: The unique function only works for vectors and not for true arrays.
Maxima
<lang maxima>unique([8, 9, 5, 2, 0, 7, 0, 0, 4, 2, 7, 3, 9, 6, 6, 2, 4, 7, 9, 8, 3, 8, 0, 3, 7, 0, 2, 7, 6, 0]); [0, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
MUMPS
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. If the indices are strings containing the separator string, they'll be split apart.
<lang MUMPS>REMDUPE(L,S)
;L is the input listing ;S is the separator between entries ;R is the list to be returned NEW Z,I,R FOR I=1:1:$LENGTH(L,S) SET Z($PIECE(L,S,I))="" ;Repack for return SET I="",R="" FOR SET I=$O(Z(I)) QUIT:I="" SET R=$SELECT($L(R)=0:I,1:R_S_I) KILL Z,I QUIT R</lang>
Example:
USER>W $$REMDUPE^ROSETTA("1,2,3,4,5,2,5,""HELLO"",42,""WORLD""",",") 1,2,3,4,5,42,"HELLO","WORLD"
Nemerle
<lang Nemerle>using System.Console;
module RemDups {
Main() : void { def nums = array[1, 4, 6, 3, 6, 2, 7, 2, 5, 2, 6, 8]; def unique = $[n | n in nums].RemoveDuplicates(); WriteLine(unique); }
}</lang>
NetRexx
This sample takes advantage of the NetRexx built-in Rexx object's indexed string capability (associative arrays). Rexx indexed strings act very like hash tables: <lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary
-- Note: Task requirement is to process "arrays". The following converts arrays into simple lists of words: -- Putting the resulting list back into an array is left as an exercise for the reader. a1 = [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] a2 = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'] a3 = ['Now', 'is', 'the', 'time', 'for', 'all', 'good', 'men', 'to', 'come', 'to', 'the', 'aid', 'of', 'the', 'party.'] x = 0 lists = x = x + 1; lists[0] = x; lists[x] = array2wordlist(a1) x = x + 1; lists[0] = x; lists[x] = array2wordlist(a2) x = x + 1; lists[0] = x; lists[x] = array2wordlist(a3)
loop ix = 1 to lists[0]
nodups_list = remove_dups(lists[ix]) say ix.right(4)':' lists[ix] say .right(4)':' nodups_list say end ix
return
-- ============================================================================= method remove_dups(list) public static
newlist = nodups = '0' loop w_ = 1 to list.words() ix = list.word(w_) nodups[ix] = nodups[ix] + 1 -- we can even collect a count of dups if we want end w_ loop k_ over nodups newlist = newlist k_ end k_
return newlist.space
-- ============================================================================= method array2wordlist(ra = Rexx[]) public static
wordlist = loop r_ over ra wordlist = wordlist r_ end r_
return wordlist.space
</lang> Output:
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 : 13 2 3 17 19 7. 4.4 5 222 7 -100.2 1.1 cats 0 11 2: 1 2 3 a b c 2 3 4 b c d : c 2 d 3 4 a b 1 3: Now is the time for all good men to come to the aid of the party. : Now aid for men to the party. come time of is all good
NewLISP
<lang NewLISP>(unique '(1 2 3 a b c 2 3 4 b c d))</lang>
Nial
<lang nial>uniques := [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'] cull uniques =+-+-+-+-+-+-+-+-+ =|1|2|3|a|b|c|4|d| =+-+-+-+-+-+-+-+-+</lang>
Using strand form <lang nial>cull 1 1 2 2 3 3 =1 2 3</lang>
Nimrod
<lang nimrod>import sequtils, algorithm, intsets
- Go through the list, and for each element, check the rest of the list to see
- if it appears again,
var items = @[1, 2, 3, 2, 3, 4, 5, 6, 7] echo deduplicate(items) # O(n^2)
proc filterDup(xs): seq[int] =
result = @[xs[0]] var last = xs[0] for x in xs[1..xs.high]: if x != last: result.add(x) last = x
- Put the elements into a hash table which does not allow duplicates.
var s = initIntSet() for x in items:
s.incl(x)
echo s
- Sort the elements and remove consecutive duplicate elements.
sort(items, system.cmp[int]) # O(n log n) echo filterDup(items) # O(n)</lang>
Objective-C
<lang objc>NSArray *items = [NSArray arrayWithObjects:@"A", @"B", @"C", @"B", @"A", nil];
NSSet *unique = [NSSet setWithArray:items];</lang>
Objeck
<lang objeck> use Structure;
bundle Default {
class Unique { function : Main(args : String[]) ~ Nil { nums := [1, 1, 2, 3, 4, 4]; unique := IntVector->New();
each(i : nums) { n := nums[i]; if(unique->Has(n) = false) { unique->AddBack(n); }; };
each(i : unique) { unique->Get(i)->PrintLine(); }; } }
} </lang>
OCaml
<lang ocaml>let uniq lst =
let unique_set = Hashtbl.create (List.length lst) in List.iter (fun x -> Hashtbl.replace unique_set x ()) lst; Hashtbl.fold (fun x () xs -> x :: xs) unique_set []
let _ =
uniq [1;2;3;2;3;4]</lang>
Another solution (preserves order of first occurrence): <lang ocaml>let uniq lst =
let seen = Hashtbl.create (List.length lst) in List.filter (fun x -> let tmp = not (Hashtbl.mem seen x) in Hashtbl.replace seen x (); tmp) lst
let _ =
uniq [1;2;3;2;3;4]</lang>
Octave
<lang octave> input=[1 2 6 4 2 32 5 5 4 3 3 5 1 2 32 4 4]; output=unique(input); </lang>
ooRexx
<lang ooRexx> data = .array~of(1, 2, 3, "a", "b", "c", 2, 3, 4, "b", "c", "d") uniqueData = .set~new~union(data)~makearray~sort
say "Unique elements are" say do item over uniqueData
say item
end </lang>
Oz
The following solutions only works if the value type is allowed as a key in a dictionary.
<lang oz>declare
fun {Nub Xs} D = {Dictionary.new} in for X in Xs do D.X := unit end {Dictionary.keys D} end
in
{Show {Nub [1 2 1 3 5 4 3 4 4]}}</lang>
PARI/GP
Sort and remove duplicates. Other methods should be implemented as well. <lang parigp>rd(v)={
vecsort(v,,8)
};</lang>
Pascal
<lang pascal>Program RemoveDuplicates;
const
iArray: array[1..7] of integer = (1, 2, 2, 3, 4, 5, 5);
var
rArray: array[1..7] of integer; i, pos, last: integer; newNumber: boolean;
begin
rArray[1] := iArray[1]; last := 1; pos := 1; while pos < high(iArray) do begin inc(pos); newNumber := true; for i := low(rArray) to last do if iArray[pos] = rArray[i] then begin newNumber := false;
break;
end; if newNumber then begin inc(last); rArray[last] := iArray[pos]; end; end; for i := low(rArray) to last do writeln (rArray[i]);
end.</lang> Output:
% ./RemoveDuplicates 1 2 3 4 5
Perl
(this version even preserves the order of first appearance of each element) <lang perl>use List::MoreUtils qw(uniq);
my @uniq = uniq qw(1 2 3 a b c 2 3 4 b c d);</lang>
It is implemented like this: <lang perl>my %seen; my @uniq = grep {!$seen{$_}++} qw(1 2 3 a b c 2 3 4 b c d);</lang>
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: <lang perl>my %hash = map { $_ => 1 } qw(1 2 3 a b c 2 3 4 b c d); my @uniq = keys %hash;</lang>
Alternately: <lang perl>my %seen; @seen{qw(1 2 3 a b c 2 3 4 b c d)} = (); my @uniq = keys %seen;</lang>
Perl 6
<lang perl6>my @unique = [1, 2, 3, 5, 2, 4, 3, -3, 7, 5, 6].uniq;</lang> Or just make a set of it. <lang perl6>set(1,2,3,5,2,4,3,-3,7,5,6).list</lang>
PHP
<lang php>$list = array(1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'); $unique_list = array_unique($list);</lang>
PicoLisp
There is a built-in function <lang PicoLisp>(uniq (2 4 6 1 2 3 4 5 6 1 3 5))</lang> Output:
-> (2 4 6 1 3 5)
PL/I
<lang PL/I>
declare t(20) fixed initial (1, 5, 6, 2, 1, 7, 5, 22, 4, 19, 1, 1, 6, 6, 6, 8, 9, 10, 11, 12); declare (i, j, k, n, e) fixed;
n = hbound(t,1); i = 0;
outer:
do k = 1 to n; e = t(k); do j = k-1 to 1 by -1; if e = t(j) then iterate outer; end; i = i + 1; t(i) = e; end;
put skip list ('Unique elements are:'); put edit ((t(k) do k = 1 to i)) (skip, f(11));
</lang>
Pop11
<lang pop11>;;; Initial array lvars ar = {1 2 3 2 3 4};
- Create a hash table
lvars ht= newmapping([], 50, 0, true);
- Put all array as keys into the hash table
lvars i; for i from 1 to length(ar) do
1 -> ht(ar(i))
endfor;
- Collect keys into a list
lvars ls = []; appdata(ht, procedure(x); cons(front(x), ls) -> ls; endprocedure);</lang>
PowerShell
The common array for both approaches: <lang powershell>$data = 1,2,3,1,2,3,4,1</lang> Using a hash table to remove duplicates: <lang powershell>$h = @{} foreach ($x in $data) {
$h[$x] = 1
}
$h.Keys</lang>
Sorting and removing duplicates along the way can be done with the Sort-Object
cmdlet.
<lang powershell>$data | Sort-Object -Unique</lang>
Removing duplicates without sorting can be done with the Select-Object
cmdlet.
<lang powershell>$data | Select-Object -Unique</lang>
PostScript
<lang postscript>
[10 8 8 98 32 2 4 5 10 ] dup length dict begin aload let* currentdict {pop} map end
</lang>
Prolog
<lang prolog>uniq(Data,Uniques) :- sort(Data,Uniques).</lang>
Example usage: <lang prolog>?- uniq([1, 2, 3, 2, 3, 4],Xs). Xs = [1, 2, 3, 4]</lang>
Because sort/2 is GNU prolog and not ISO here is an ISO compliant version:
<lang prolog>member1(X,[H|_]) :- X==H,!.
member1(X,[_|T]) :- member1_(X,T).
distinct([],[]). distinct([H|T],C) :- member1(H,T),!, distinct(T,C). distinct([H|T],[H|C]) :- distinct(T,C).</lang>
Example usage: <lang prolog>?- distinct([A, A, 1, 2, 3, 2, 3, 4],Xs). Xs = [A, 1, 2, 3, 4]</lang>
PureBasic
Task solved with the built in Hash Table which are called Maps in PureBasic <lang PureBasic>NewMap MyElements.s()
For i=0 To 9 ;Mark 10 items at random, causing high risk of duplication items.
x=Random(9) t$="Number "+str(x)+" is marked" MyElements(str(x))=t$ ; Add element 'X' to the hash list or overwrite if already included.
Next
ForEach MyElements()
Debug MyElements()
Next</lang> Output may look like this, e.g. duplicated items are automatically removed as they have the same hash value.
Number 0 is marked Number 2 is marked Number 5 is marked Number 6 is marked
Python
If all the elements are hashable (this excludes list, dict, set, and other mutable types), we can use a set: <lang python>items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'] unique = list(set(items))</lang>
If all the elements are comparable (i.e. <, >=, etc. operators; this works for list, dict, etc. but not for complex and many other types, including most user-defined types), we can sort and group: <lang python>import itertools items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'] unique = [k for k,g in itertools.groupby(sorted(items))]</lang>
If both of the above fails, we have to use the brute-force method, which is inefficient: <lang python>items = [1, 2, 3, 'a', 'b', 'c', 2, 3, 4, 'b', 'c', 'd'] unique = [] for x in items:
if x not in unique: unique.append(x)</lang>
See also http://www.peterbe.com/plog/uniqifiers-benchmark and http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
Qi
<lang qi> (define remove-duplicates
[] -> [] [A|R] -> (remove-duplicates R) where (element? A R) [A|R] -> [A|(remove-duplicates R)])
(remove-duplicates [a b a a b b c d e]) </lang>
R
<lang r>items <- c(1,2,3,2,4,3,2) unique (items)</lang>
Racket
Using the built-in function <lang Racket> -> (remove-duplicates '(2 1 3 2.0 a 4 5 b 4 3 a 7 1 3 x 2)) '(2 1 3 2.0 a 4 5 b 7 x) </lang>
Using a hash-table: <lang Racket> (define (unique/hash lst)
(hash-keys (for/hash ([x (in-list lst)]) (values x #t))))
</lang>
Using a set: <lang Racket> (define unique/set (compose1 set->list list->set)) </lang>
A definition that works with arbitrary sequences and allows specification of an equality predicate.
<lang Racket> (define (unique seq #:same-test [same? equal?])
(for/fold ([res '()]) ([x seq] #:unless (memf (curry same? x) res)) (cons x res)))
</lang>
-> (unique '(2 1 3 2.0 a 4 5 b 4 3 a 7 1 3 x 2)) '(1 2 3 a b x 4 5 7 2.0) -> (unique '(2 1 3 2.0 4 5 4.0 3 7 1 3 2) #:same-test =) '(7 5 4 3 1 2) -> (unique #(2 1 3 2.0 4 5 4.0 3 7 1 3 2)) '(7 5 4 3 1 2) -> (apply string (unique "absbabsbdbfbd")) "fdsba"
REBOL
<lang REBOL>print mold unique [1 $23.19 2 elbow 3 2 Bork 4 3 elbow 2 $23.19]</lang>
Output:
[1 $23.19 2 elbow 3 Bork 4]
Raven
<lang raven>[ 1 2 3 'a' 'b' 'c' 2 3 4 'b' 'c' 'd' ] as items items copy unique print
list (8 items)
0 => 1 1 => 2 2 => 3 3 => "a" 4 => "b" 5 => "c" 6 => 4 7 => "d"</lang>
REXX
Note that in REXX, strings are quite literal.
- +7 is different from 7 (but compares numerically equal).
- 00 is different from 0 (but compares numerically equal).
- -0 is different from 0 (but compares numerically equal).
- 7. is different from 7 (but compares numerically equal).
- Ab is different from AB (but can compare equal if made case insensitive).
Note that all three REXX examples below don't care what type of element is used,
integer, floating point, character, binary, ...
version 1, using a modified method 3
Instead of discard an element if it's a duplicated, it just doesn't add it to the new list.
This method is faster than method 3.
<lang rexx>/*REXX program to remove duplicate elements (items) in a list. */
$= '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'
say 'original list:' $
say right(words($),13) ' words in the original list.'; say
do j=words($) by -1 to 1; y=word($,j) /*process words in the list, */ _=wordpos(y, $, j+1); if _\==0 then $=delword($, _, 1) /*del if dup.*/ end /*j*/
say 'modified list:' space($) say right(words($),13) ' words in the modified list.'
/*stick a fork in it, we're done.*/</lang>
output
original list: 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 23 words in the original list. modified list: 2 3 5 7 11 13 17 19 cats 222 -100.2 +11 1.1 +7 7. 0 4.4 17 words in the modified list.
version 2, using method 3
<lang rexx>/*REXX program to remove duplicate elements (items) in a list. */ old= '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' say 'original list:' old say right(words(old),13) ' words in the original list.'; say new= /*start with a clean slate. */
do j=1 for words(old); _=word(old,j) /*process the words in old list. */ if wordpos(_,new)==0 then new=new _ /*Doesn't exist? Then add to list*/ end /*j*/
say 'modified list:' space(new) say right(words(new),13) ' words in the modified list.'
/*stick a fork in it, we're done.*/</lang>
output is identical to the 1st version.
version 3, using method 1 (hash table) via REXX stems
<lang rexx>/* REXX ************************************************************
- 26.11.2012 Walter Pachl
- added: show multiple occurrences
- /
old='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'
say 'old list='old say 'words in the old list=' words(old) new= found.=0 count.=0 Do While old<>
Parse Var old w old If found.w=0 Then Do new=new w found.w=1 End count.w=count.w+1 End
say 'new list='strip(new) say 'words in the new list=' words(new) Say 'Multiple occurrences:' Say 'occ word' Do While new<>
Parse Var new w new If count.w>1 Then Say right(count.w,3) w End</lang>
Output:
old list=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 words in the old list= 23 new list=2 3 5 7 11 13 17 19 cats 222 -100.2 +11 1.1 +7 7. 0 4.4 words in the new list= 17 Multiple occurrences: occ word 3 2 2 3 3 5 2 7
Ruby
Ruby has an Array#uniq
built-in method, which returns a new array by removing duplicate values in self.
<lang ruby>ary = [1,1,2,1,'redundant',[1,2,3],[1,2,3],'redundant']
p ary.uniq # => [1, 2, "redundant", [1, 2, 3]]</lang>
You can also write your own uniq method. <lang ruby>class Array
# used Hash def uniq1 each_with_object({}) {|elem, h| h[elem] = true}.keys end # sort (requires comparable) def uniq2 sorted = sort pre = sorted.first sorted.each_with_object([pre]){|elem, uniq| uniq << (pre = elem) if elem != pre} end # go through the list def uniq3 each_with_object([]) {|elem, uniq| uniq << elem unless uniq.include?(elem)} end
end
ary = [1,1,2,1,'redundant',[1,2,3],[1,2,3],'redundant'] p ary.uniq1 #=> [1, 2, "redundant", [1, 2, 3]] p ary.uniq2 rescue nil # Error (not comparable) p ary.uniq3 #=> [1, 2, "redundant", [1, 2, 3]]
ary = [1,2,3,7,6,5,2,3,4,5,6,1,1,1] p ary.uniq1 #=> [1, 2, 3, 7, 6, 5, 4] p ary.uniq2 #=> [1, 2, 3, 4, 5, 6, 7] p ary.uniq3 #=> [1, 2, 3, 7, 6, 5, 4]</lang>
A version without implementing class declarations: <lang ruby> def unique(array)
pure = Array.new for i in array flag = false for j in pure flag = true if j==i end pure << i unless flag end return pure
end
unique ["hi","hey","hello","hi","hey","heyo"] # => ["hi", "hey", "hello", "heyo"]
unique [1,2,3,4,1,2,3,5,1,2,3,4,5] # => [1,2,3,4,5]
</lang>
Scala
<lang scala>val list = List(1,2,3,4,2,3,4,99) val l2 = list.distinct // l2: scala.List[scala.Int] = List(1,2,3,4,99)
val arr = Array(1,2,3,4,2,3,4,99) val arr2 = arr.distinct // arr2: Array[Int] = Array(1, 2, 3, 4, 99) </lang>
Scheme
<lang scheme>(define (remove-duplicates l)
(cond ((null? l) '()) ((member (car l) (cdr l)) (remove-duplicates (cdr l))) (else (cons (car l) (remove-duplicates (cdr l))))))
(remove-duplicates '(1 2 1 3 2 4 5))</lang>
<lang scheme>(1 3 2 4 5)</lang>
Alternative approach: <lang scheme>(define (remove-duplicates l)
(do ((a '() (if (member (car l) a) a (cons (car l) a))) (l l (cdr l))) ((null? l) (reverse a))))
(remove-duplicates '(1 2 1 3 2 4 5))</lang>
<lang scheme>(1 2 3 4 5)</lang>
The function 'delete-duplicates' is also available in srfi-1.
Seed7
<lang seed7>$ include "seed7_05.s7i";
const proc: main is func
local const array integer: data is [] (1, 3, 2, 9, 1, 2, 3, 8, 8, 1, 0, 2); var set of integer: dataSet is (set of integer).value; var integer: number is 0; begin for number range data do incl(dataSet, number); end for; writeln(dataSet); end func;</lang>
Output:
{0, 1, 2, 3, 8, 9}
SETL
<lang SETL>items := [0,7,6,6,4,9,7,1,2,3,2]; print(unique(items));</lang> Output in arbitrary order (convert tuple->set then set->tuple): <lang SETL>proc unique(items);
return [item: item in {item: item in items}];
end proc;</lang>
Preserving source order <lang SETL>proc unique(items);
seen := {}; return [item: item in items, nps in {#seen} | #(seen with:= item) > nps];
end proc;</lang>
Sidef
<lang ruby>var ary = [1,1,2,1,'redundant',[1,2,3],[1,2,3],'redundant']; say ary.uniq.dump; say ary.last_uniq.dump;</lang>
- Output:
[1, 2, 'redundant', [1, 2, 3]] [2, 1, [1, 2, 3], 'redundant']
Slate
<lang slate>[|:s| #(1 2 3 4 1 2 3 4) >> s] writingAs: Set.
"==> {"Set traitsWindow" 1. 2. 3. 4}"</lang>
Smalltalk
<lang smalltalk>"Example of creating a collection" |a| a := #( 1 1 2 'hello' 'world' #symbol #another 2 'hello' #symbol ). a asSet.</lang> Output:
Set (1 2 #symbol 'world' #another 'hello' )
the above has the disadvantage of loosing the original order (because Sets are unordered, and the hashing shuffles elements into an arbitrary order). When tried, I got:
Set('world' 1 #another 'hello' #symbol 2)
on my system. This can be avoided by using an ordered set (which has also O(n) complexity) as below:
<lang smalltalk>|a| a := #( 1 1 2 'hello' 'world' #symbol #another 2 'hello' #symbol ). a asOrderedSet.</lang> Output:
OrderedSet(1 2 'hello' 'world' #symbol #another)
Sparkling
<lang sparkling>function undupe(arr) { var t = {}; foreach(arr, function(key, val) { t[val] = true; });
var r = {}; foreach(t, function(key) { r[sizeof r] = key; });
return r; }</lang>
Tcl
The concept of an "array" in Tcl is strictly associative - and since there cannot be duplicate keys, there cannot be a redundant element in an array. What is called "array" in many other languages is probably better represented by the "list" in Tcl (as in LISP). With the correct option, the lsort
command will remove duplicates.
<lang tcl>set result [lsort -unique $listname]</lang>
TUSCRIPT
<lang tuscript> $$ MODE TUSCRIPT list_old="b'A'A'5'1'2'3'2'3'4" list_sort=MIXED_SORT (list_old) list_new=REDUCE (list_sort) PRINT list_old PRINT list_new </lang> Output (sorted)
b'A'A'5'1'2'3'2'3'4 1'2'3'4'5'A'b
or <lang tuscript> $$ MODE TUSCRIPT list_old="b'A'A'5'1'2'3'2'3'4" DICT list CREATE LOOP l=list_old DICT list LOOKUP l,num IF (num==0) DICT list ADD l ENDLOOP DICT list unload list list_new=JOIN (list) PRINT list_old PRINT list_new </lang> Output:
b'A'A'5'1'2'3'2'3'4 b'A'5'1'2'3'4
UnixPipes
Assuming a sequence is represented by lines in a file. <lang bash>bash$ # original list bash$ printf '6\n2\n3\n6\n4\n2\n' 6 2 3 6 4 2 bash$ # made uniq bash$ printf '6\n2\n3\n6\n4\n2\n'|sort -n|uniq 2 3 4 6 bash$</lang>
or
<lang bash>bash$ # made uniq bash$ printf '6\n2\n3\n6\n4\n2\n'|sort -nu 2 3 4 6 bash$</lang>
Ursala
The algorithm is to partition the list by equality and take one representative from each class, which can be done by letting the built in partition operator, |=, use its default comparison relation. This works on lists of any type including character strings but the comparison is based only on structural equivalence. It's up to the programmer to decide whether that's a relevant criterion for equivalence or else specify a better one. <lang Ursala>#cast %s
example = |=hS& 'mississippi'</lang> output:
'mspi'
Vedit macro language
The input "array" is an edit buffer where each line is one element. <lang vedit>Sort(0, File_Size) // sort the data While(Replace("^(.*)\N\1$", "\1", REGEXP+BEGIN+NOERR)){} // remove duplicates</lang>
Vim Script
<lang vim>call filter(list, 'count(list, v:val) == 1')</lang>
Wart
<lang python>def (dedup l)
let exists (table) collect+each x l unless exists.x yield x exists.x <- 1</lang>
Output:
dedup '(1 3 2 9 1 2 3 8 8 1 0 2) => (1 3 2 9 8 0)
Wortel
<lang wortel>@uniq [1 2 3 2 1 2 3] ; returns [1 2 3]</lang>
XPL0
<lang XPL0>code Text=12; \built-in routine to display a string of characters string 0; \use zero-terminated strings (not MSb terminated)
func StrLen(S); \Return number of characters in an ASCIIZ string char S; int I; for I:= 0, -1>>1-1 do \(limit = 2,147,483,646 if 32 bit, or 32766 if 16 bit)
if S(I) = 0 then return I;
func Unique(S); \Remove duplicate bytes from string char S; int I, J, K, L; [L:= StrLen(S); \string length for I:= 0 to L-1 do \for all characters in string...
for J:= I+1 to L-1 do \scan rest of string for duplicates if S(I) = S(J) then \if duplicate then [for K:= J+1 to L do \ shift rest of string down (including S(K-1):= S(K); \ terminating zero) L:= L-1 \ string is now one character shorter ];
return S; \return pointer to string ];
Text(0, Unique("Pack my box with five dozen liquor jugs."))</lang>
- Output:
Pack myboxwithfvedznlqurjgs.
zkl
Using built ins: <lang zkl>zkl: Utils.Helpers.listUnique(T(1,3,2,9,1,2,3,8,8,"8",1,0,2,"8")) L(1,3,2,9,8,"8",0) zkl: "1,3,2,9,1,2,3,8,8,1,0,2".unique() ,012389</lang> Where listUnique is brute force: <lang zkl>fcn listUnique(xs){
xs.reduce(fcn(us,s){us.holds(s) and us or us.append(s)},L()) }</lang>