Distinct Sieves

Question

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 code-golf 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.

Answer 1

MATL, 7 6 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

Answer 2

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.

Answer 3

Python 3, 47 35 39 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

Answer 4

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.

Answer 5

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.

Answer 6

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!.

Answer 7

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

Answer 8

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();
    }

Answer 9

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.

Answer 10

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.

Answer 11

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

Answer 12

JavaScript (ES6), 31 bytes

f=a=>a.map((e,i)=>i-a.indexOf(e))

Zero is truthy and other numbers are falsy.

Answer 13

Mathematica, 53 31 bytes

Thanks to miles for giving me an idea that saved 22 bytes.

s[[;;x++]]~FreeQ~#&/@(x=0;s=#)&

Answer 14

Perl 5

push@o,map{$b=pop@a;(grep{/^$b$/}@a)?1:0}(1..~~@a);

Answer 15

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.

Verify all testcases.

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;
    }
}

Answer 16

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

Answer 17

Pyke, 4 bytes

F@oq

Try it here!

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

Answer 18

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});
}

Answer 19

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

Answer 20

PHP, 66 62 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>';

Answer 21

Haskell, 29 27 bytes

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.

Answer 22

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..

Answer 23

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!

Answer 24

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.