# Distinct Sieves

Given a list of integers, create a boolean mask such that the true indices can be used to filter the distinct values from the list. Which index is selected as the true one does not matter as long as only one of them is selected for each set of indices corresponding to identical values.

The input will be a non-empty list of non-negative integers in a format suitable for your language and the output will be a list of boolean values following the specification above. You are allowed to use your own definitions of truthy and falsy values in the output list.

In my examples below, I define 1 to be truthy and 0 to be falsy.

[5, 4, 7, 1]  Input
[1, 1, 1, 1]  Output
Select only the values with with true indicies in the sieve
[5  4  7  1]  Contains zero duplicate values

[5, 9, 7, 5, 6, 0, 5]
[0, 1, 1, 1, 1, 1, 0]
[   9, 7, 5, 6, 0   ]


## Test Cases

When there is an or, it means that there are multiple valid outputs. If there is a trailing ellipsis ... after the or, it means that not all of the possible outputs were listed.

[0] = [1]

[55] = [1]

[32, 44] = [1, 1]

[0, 0] = [1, 0] or [0, 1]

[9001, 9001, 9001] = [1, 0 , 0] or [0, 1, 0] or [0, 0, 1]

[5, 4, 7, 1] = [1, 1, 1, 1]

[1, 2, 3, 4, 3, 5] = [1, 1, 1, 1, 0, 1] or
[1, 1, 0, 1, 1, 1]

[5, 9, 7, 5, 6, 0, 5] = [1, 1, 1, 0, 1, 1, 0] or
[0, 1, 1, 1, 1, 1, 0] or
[0, 1, 1, 0, 1, 1, 1]

[0, 8, 6, 6, 3, 8, 7, 2] = [1, 1, 1, 0, 1, 0, 1, 1] or
[1, 0, 0, 1, 1, 1, 1, 1] or
[1, 0, 1, 0, 1, 1, 1, 1] or
[1, 1, 0, 1, 1, 0, 1, 1]

[45, 47, 47, 45, 24, 24, 24, 8, 47, 41, 47, 88]
= [1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1] or ...

[154, 993, 420, 154, 154, 689, 172, 417, 790, 175, 790, 790, 154, 172, 175, 175, 420, 417, 154, 175, 172, 175, 172, 993, 689, 993, 993, 790]
= [1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] or ...


## Rules

• This is so the shortest solution wins.
• Builtins are allowed!
• You are allowed to use your own definitions of truthy and falsy values in the output list. If you choose to do so, please state your definitions.
• The input will be a non-empty list of non-negative integers.
• You are free to choose between outputting only one of the sieves or multiple or even all of them. As long as each sieve is valid, it will be accepted.
• For [0, 8, 6, 6, 3, 8, 7, 2], should [1, 0, 0, 1, 1, 1, 1, 1] be added to the list of valid outputs? Jul 2, 2016 at 14:52
• Does your own definitions of truthy and falsy values refer to the language or can we choose freely? Do they have to be consistent? Jul 2, 2016 at 15:17
• @atlasologist Thanks for catching the typo Jul 2, 2016 at 15:53
• @Dennis You are free to define your own boolean values, they do not have to be the same as the language you choose, but you have to be consistent with your own definitions. Instead of 1 and 0 for true and false in my examples, I could have done negative values as false and non-negative (zero or positive) values as true. Jul 2, 2016 at 15:56
• OK, thanks for clarifying. By consistent, I meant if there has to be a single truthy value or if there can be several. Jul 2, 2016 at 15:57

# MATL, 76 4 bytes

1 byte saved thanks to @Luis
2 bytes saved thanks to @Dennis

&=Rs


We define 1 to be truthy and all other values as falsey

Try it Online

All test cases

Explanation

    % Implicitly grab input array
&=  % 2D array of equality comparisons
R   % Get the upper triangular portion
s   % Sum down the columns
% Implicitly display the result

• 1 byte fewer: &=Rs1= Jul 2, 2016 at 14:41
• @LuisMendo Ha I was literally just playing with that approach! Jul 2, 2016 at 14:41
• The OP has clarified what truthy and falsy mean in this challenge. If you define 1 as truthy and everything else as falsy, you can drop the l=. Jul 2, 2016 at 16:05
• Great use. The intent was to avoid having to add a filtering step and now you've matched Dennis' Jelly solution. Jul 2, 2016 at 16:11

# Jelly, 4 bytes

ĠṪ€Ṭ


Favors last occurrences. Try it online! or verify all test cases.

### How it works

ĠṪ€Ṭ  Main link. Argument: A (array)

Ġ     Group; paritition the indices of A according to their corresponding values.
Ṫ€   Tail each; select the last index of each group.
Ṭ  Untruth; generate a Boolean array with 1's at the specified indices.

• Would this not chop off the zeroes at the end? Jul 3, 2016 at 11:47
• There can't be a zero at the end, because we select the last occurrence of each unique integer. Jul 3, 2016 at 15:26
• That's clever . Jul 3, 2016 at 16:04

## Python 3, 473539 36 bytes

lambda n:[n.pop(0)in n for x in n*1]


Pops the first item from the list, checks if it exists elsewhere in the list, and inserts True or False into a new list.

For this function, False indicates a distinct value, and True is otherwise (True=0 and False=1)

Thanks to Dennis for a ton of bytes

Original, 47 bytes:

lambda n:[(1,0)[n.pop()in n]for x in[1]*len(n)]


Try it

• lambda n:[1-(n.pop()in n)for x in n*1] saves a few bytes. Jul 2, 2016 at 15:27
• The OP has clarified that the truthy value doesn't actually have to be truthy, so lambda n:[n.pop()in n for x in n*1] works as well. Jul 2, 2016 at 15:59
• The new version had me lost for a bit until I realized it used the negated values like xnor did for truthy and falsy. Jul 2, 2016 at 18:59
• You need to do .pop(0) or the mask comes out reversed.
– xnor
Jul 2, 2016 at 20:17
• That not what xnor meant. .pop() processes the last element first, so the are in reversed order. Jul 2, 2016 at 23:30

# Pyth, 6 bytes

.eqxQb


Outputs a list of bools (True and False). Checks for each element in the input, if its index is equal to the index of the first occurence of the value. In other words, this is checking if each element is the first occurence.

In pythonic pseudocode:

.e      enumerated_map(lambda b,k:    # maps with b as value and k as index
q       equal(
xQb      Q.index(b),
k),                       # implicit lambda variable
Q)                          # implicit argument to map


Test it here.

# J, 2 bytes

~:


This was where the idea for this challenge originated from. The builtin ~: is called Nub-Sieve in J and creates a boolean list that performs the operation described in the challenge. Here, 1 represents true and 0 represents false.

# 05AB1E, 8 bytes

Code:

v¹ykN>Qˆ


Explanation:

y         # For each in the array
¹yk      # Get the index of that element in the array
N>Q   # And see if it's equal to the index
ˆ  # Add to the global array and implicitly output


Uses the CP-1252 encoding. Try it online!.

# APL, 6 bytes

⍳∘⍴∊⍳⍨


Try it

Explanation:

   ⍳⍨  For each character in the string, get the index of its first occurrence
⍳∘⍴     Make a list 1 .. length of input
∊    Check if each index is present


## C#, 63 bytes

int[]l(List<int> i)=>i.Select((m,n)=>i.IndexOf(m)-n).ToArray();


I could also make it return 1 or 0 and therby make the parameter and return type the same one therby allowing me to make this a lambda expression by itself?

some guidance would be appreciated

same type code

    public static List<int>l(List<int>i){
return i.Select((m,n)=>i.IndexOf(m)==n?1:0).ToList();
}

• if you define truthy to be 0 and falsy to be anything else you can replace the ==n with -n and return a int[] Jul 4, 2016 at 14:48
• thats a great idea Jul 4, 2016 at 14:49
• also use expression bodied function int[]l(List<int>i)=>i.Select((m,n)=>i.IndexOf(m)-n).ToArray(); Jul 4, 2016 at 14:52
• oh my god, thats saving so many bytes in my answers from now on. thank you so much Jul 4, 2016 at 14:57
• Can you provide an example on .NetFiddle? Jul 4, 2016 at 15:02

## Python, 35 bytes

f=lambda l:l and[l.pop(0)in l]+f(l)


Uses True as the falsy value and False for the truthy value. Marks the last appearance of each element.

Selects the first element only if it doesn't appear among the remaining elements, then recurses to the rest of the list as long as it's non-empty. The l.pop(0) extracts the first element while also removing it.

## Retina, 23 bytes

(\d+)((?!.* \1\b))?
$#2  Input is a space-separated list. (Actually, other formats like [1, 2, 3] will also work as long as there's a space in front of each number except the first.) Try it online! (Works on multiple linefeed-separated test cases at once.) We simply turn each element into 0 if there's another copy of it later on in the input and into 1 otherwise. ## PowerShell v2+, 40 bytes $a=@();$args[0]|%{(1,0)[$_-in$a];$a+=$_}  Creates an empty array $a. Then we take the input list via $args[0] and pipe that into a loop |%{...}. Each iteration we select either 1 or 0 from a pseudo-ternary based on whether the current element is in $a or not. Those selections are left on the pipeline. We then add the current element into the array $a. The pipeline elements are gathered up, and output as an array is implicit. ### Example: (output here with a newline separator, since that's the default .ToString() for an array) PS C:\Tools\Scripts\golfing> .\distinct-sieves.ps1 1,2,3,4,1,3,5,7 1 1 1 1 0 0 1 1  ## JavaScript (ES6), 31 bytes f=a=>a.map((e,i)=>i-a.indexOf(e))  Zero is truthy and other numbers are falsy. ## Mathematica, 53 31 bytes Thanks to miles for giving me an idea that saved 22 bytes. s[[;;x++]]~FreeQ~#&/@(x=0;s=#)&  • How about using MapIndexed over the previous sublists? MapIndexed[s[[;;#-1&@@#2]]~FreeQ~#&,s=#]& takes 41 bytes. Jul 2, 2016 at 19:14 • @miles Ohh, that's much better (and I improved it a bit more ;)) Jul 2, 2016 at 19:19 • Oo that's a nice way to shorten MapIndexed for this case and you don't even have to extract or decrement the index Jul 2, 2016 at 19:28 ## Perl 5 push@o,map{$b=pop@a;(grep{/^$b$/}@a)?1:0}(1..~~@a);

• 1. .. provides scalar context, so you shouldn't need ~~. 2. grep returns truthy/falsy, so you shouldn't need ?1:0. 3. grep/.../,@a is shorter than grep{/.../}@a. 4. You shouldn't need the final ;. 5. You shouldn't need the parentheses around 1..@a. 6. You don't show where the input is coming from or the output is going to: see meta.codegolf.stackexchange.com/q/2447 Jul 11, 2016 at 18:21

# Java, 96 bytes

void s(int[]a){for(int i=0,j,n=a.length,b=1;i<n;a[i++]=b,b=1)for(j=i+1;j<n;)b=a[i]==a[j++]?0:b;}


Modifies the array in-place. Favours the last occurrence.

The truthy value is 1 while the falsey value is 0.

Ungolfed:

void sieve(int[]a){
int n = a.length;
for(int i=0;i<n;i++){
int b = 1;
for(int j=i+1;j<n;j++){
if(a[i] == a[j]){
b = 0;
}
}
a[i] = b;
}
}


## Actually, 11 bytes

;╗ñi@╜í=M


Try it online!

Explanation:

;╗ñi@╜í=M
;╗           save a copy of input in reg0
ñ          enumerate
i@╜í=M  for each (index, value) pair:
i@         flatten, swap
╜í       first index in input of value
=      compare equality


## Pyke, 4 bytes

F@oq


Try it here!

     - o = 0 #(Implicit)
F    - for i in input:
@   -   input.index(i)
q -  ^==V
o  -   o+=1


# C++, 242 bytes

Admittedly an overkill solution, as it works on any standard container of any ordered type:

#include<algorithm>
#include<list>
#include<set>
template<class T>auto f(T a){using V=typename T::value_type;std::set<V>s;std::list<bool>r;std::transform(a.begin(),a.end(),std::back_inserter(r),[&](V m){return s.insert(m).second;});return r;}


## Ungolfed:

(and further generalised)

template<class T>
auto f(T a)
{
using std::begin;
using std::end;
using V=typename T::value_type;
std::set<V>s;
std::list<bool>r;
std::transform(begin(a),end(a),std::back_inserter(r),[&](V m){return s.insert(m).second;});
return r;
}


## Test suite:

int test(const std::list<bool>& expected, const auto& x) { return f(x) != expected; }
#include<array>
#include<chrono>
#include<forward_list>
#include<initializer_list>
#include<string>
#include<vector>
using namespace std::literals::chrono_literals;
int main()
{
return 0
+ test({},            std::vector<short>{})
+ test({1},           std::array<int,1>{})
+ test({1},           std::vector<char>{55})
+ test({true,true},   std::vector<unsigned>{32,44})
+ test({1,0},         std::list<std::string>{"zero", "zero"})
+ test({1,0,0},       std::vector<long>{9001,9001,9001})
+ test({1,1,1,1},     std::array<char,4>{5,4,7,1})
+ test({1,1,1,1,0,1}, std::initializer_list<std::string>{"one","two","three","four","three","five"})
+ test({1,0,1,0,0},   std::forward_list<std::chrono::seconds>{60s, 1min, 3600s, 60min, 1h});
}


# TSQL 52 bytes

DECLARE @ TABLE(i int identity, v int)
INSERT @ values(1),(2),(3),(4),(3),(5)

SELECT i/max(i)over(partition by v)FROM @ ORDER BY i


Fiddle

# PHP, 6662 39 bytes

• accepts all atomic values (boolean, integer, float, string)
except for values evaluating to false (false, 0, "") and numeric strings ("1" equals 1)
• flags first occurence

new version (program, 37+2 bytes)
beats Java and (now again) C#. Even almost beats Python now. Happy.

<?foreach($a as$v)$u[$v]=print$u[$v]|0;

• +6 for PHP>=5.4, +16-3 for a function
• prints undelimited list of 0 (true) and 1 (false)
insert ! after print to invert
• usage: set register_globals=On, short_open_tags=On and error_reporting=0 in php.ini for php-cgi
then call php-cgi -f <filename> a[]=<value1> a[]=<value2> ...;echo"";
• for PHP>=5.4: replace $a with $_GET[a] (+6), set short_open_tags=On and error_reporting=0
• or replace $a with array_slice($argv,1) (+19), remove <?  (-2)
and call php -d error_reporting=0 -r '<code>' <value1> <value2> ...;echo""

old version (function, 62 bytes)

function f($a){foreach($a as$v)$u[$v]=1|$m[]=$u[$v];return$m;}  • returns array of false for true and true for false; (ouput as empty string or 1) insert ! after $m[]= to invert
• There is another way for a qualified function with 55 bytes, too.

tests (on old version)

function out($a){if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';} function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',(strcmp(out($y),out($e))?'N':'Y'),"</td></tr>";$h='';}
$samples=[ [0],[1], [55],[1], [32,44],[1,1], [9001,9001,9001],[1,false,false], [5,4,7,1],[1,1,1,1], [1,2,3,4,3,5],[1,1,1,1,false,1], [5,9,7,5,6,0,5],[1,1,1,false,1,1,false], [0,8,6,6,3,8,7,2],[1,1,1,false,1,false,1,1], [45,47,47,45,24,24,24,8,47,41,47,88],[1,1,'','',1,'','',1,'',1,'',1], [154,993,420,154,154,689,172,417,790,175,790,790,154,172,175, 175,420,417,154,175,172,175,172,993,689, 993,993,790], array_merge([1,1,1,false,false,1,1,1,1,1],array_fill(0,18,false)) ]; for($i=count($samples);$i--;--$i)for($j=count($samples[$i]);$j--;)$samples[$i][$j]=!$samples[$i][$j]; while($samples)
{
$a=array_shift($samples);
$em=array_shift($samples);
test($a,$em,$ym=s($a));
$eu=[];foreach($em as$i=>$f)if($f)$eu[]=$a[$i];
$yu=[];foreach($ym as$i=>$f)if($f)$yu[]=$a[$i];
#   sort($eu); sort($yu);
test('unique values',$eu,$yu);
}
echo '</table>';


f a=[elem x t|x:t<-tails a]


Uses False as true, True as false value:

λ> let f a=[elem x t|x:t<-tails a] in f [5, 9, 7, 5, 6, 0, 5]
[True,False,False,True,False,False,False]


You might have to import Data.List to use tails but, tryhaskell.org runs the code as is.

• No need for the outer parenthesis. \a->[...] is a proper function. If in doubt, give it a name: f a=[...].
– nimi
Jul 4, 2016 at 17:48
• @nimi couldn't call it without the parentheses. but giving it name works, thanks a lot. Jul 4, 2016 at 18:49
• I don’t like this justification of omitting import Data.List very much. a. is a very slippery slope as you could put any amount of imports (or even definitions!) in your GHCi config. b. treats tryhaskell.org as an authoritative implementation of the Haskell language, but it really isn’t one. (Again, what if I create my own try-Haskell-online environment that comes with all the imports and definitions golfers could ever want? Is that still really “Haskell”?)
– lynn
Jul 8, 2016 at 2:19
• I was told here once that if there is any platform that runs the code as is, then that code is acceptable. I don't know what the exact rules are, I go by what I'm told. I think yes, if your site is available 24/7, and runs standard Haskell, why not. But you're right about the first one, I removed it. Thanks. Jul 8, 2016 at 7:42

# Perl 5 + Perligata, 343 bytes

315 bytes, plus 28 for -MLingua::Romana::Perligata

Use as perl -MLingua::Romana::Perligata foo.pl; input (from stdin) and output (to stdout) are underscore-separated strings of decimal integers. Tested on Strawberry 5.20.2 with version 0.6 of Perligata; I don't know whether it works with Perligata version 0.50.

huic vestibulo perlegementum da.qis _ scindementa da.dum qis fac sic
ao qis decumulamentum da.ao aum tum nullum addementum da.meo io.meo ro.per ium in qis fac sic
si ium tum aum aequalitas fac sic ro I da cis cis
ro nullum tum non rum addementum da.capita bis rum cis
per in bis fac sic hoc tum _ egresso scribe cis


Obviously this is clear as a bell. In case it's not, run it with -MLingua::Romana::Perligata=converte instead of -MLingua::Romana::Perligata, and perl will, instead of running the script, output a translation into regular Perl:

 $_ = Lingua::Romana::Perligata::getline (*STDIN ); @q = split ( '_'); while (@q) {$a = pop (@q );
$a = ($a + 0);
my $i ; my$r ;
for $i (@q) {if ( ($i eq $a)) {$r = 1}
}
;
$r = (0 + ! ($r));
unshift (@b, $r)} ; for$_ (@b) {print (STDOUT \$_, '_')}


For a token-by-token analysis, use -MLingua::Romana::Perligata=discribe.

Golfing notes:

• Undocumented (but unsurprising), you don't need a space after ..
• (Also unsurprising,) scinde doesn't need a second argument, and uses hoc.
• I had to use ao aum tum nullum addementum da because I couldn't get morde to work.
• Similarly, I used per ium in qis... ro I da because I couldn't get vanne to work.
• Instead of huic vestibulo perlegementum da, I tried -pMLingua::Romana::Perligata, but couldn't get it to work, either.

Just for kicks (although this whole answer was just for kicks):

• After cleaning it up to Huic vestibulo perlegementum da. Qis lacunam scindementa da. Dum qis fac sic ao qis decumulamentum da. Ao aum tum nullum addementum da. Meo io. Meo ro. Per ium in qis fac sic si ium tum aum aequalitas fac sic ro I da cis cis. Ro nullum tum non rum addementum da. Capita bis rum cis. Per in bis fac sic hoc tum lacunam egresso scribe cis., Google Translate gives This court perlegementum grant. QIS gap scindementa grant. While QIS QIS decumulamentum do so ao da. Ao sum and no addementum grant. My io. My ro. Through ium in QIS do so if the sum ium equality do so ro 1 from cis. Ro was not any rum addementum grant. The heads of the bis side. Write, do so as soon as he at that time that in the gap by the Kish was taken..

# GolfScript, 19 bytes

..|:i;{i,\i\-:i,-}%


Explanation!

..|:i;{i,\i\-:i,-}% #Distinct sieve
..                  #Duplicate twice. Stack is [A A A]
|                 #Binary OR. Removes duplicates. Stack is [A (A|A)]
:i;              #Call this A|A i, and remove it from the stack. [A], i=A|A
{          }% #Block notation. For each element in the top array, perform this on it.
{i,        }% #Size of i. Element in array is [E (i,)].
{  \       }% #Swap the top two elements. [(i,) E]
{   i\     }% #Put i in the actual second position. [(i,) i E]
{     -    }% #Remove all instances of the top element from the second. [(i,) (i-E)]
{      :i  }% #This (i-E) is our new i (for the next loop).
{        , }% #Size of topmost element (either i, or i,-1 if index was found).
{         -}% #Subtract. This gives us 1 if E was removed from i, 0 otherwise.



Try it online!

# jq, 41 bytes

.[:range(length)+1]|[.[:-1][]!=.[-1]]|all


Try it online!

Takes an array, outputs a stream of jq booleans corresponding to its distinct sieve.

-10 from ovs.

• If you use vectorized != and all instead of index and not, you don't need the assignment: .[:range(length)+1]|[.[:-1][]!=.[-1]]|all
– ovs
Sep 6, 2021 at 8:39
• great method to remove the variable. Thanks. Sep 6, 2021 at 9:07