Generate an arbitrary half of a string

Question

Given a string \$ x \$, we say another string \$ y \$ is half of it, if both of the following properties are true:

• \$ y \$ is a (not necessarily continuous) subsequence of \$ x \$ - there exists a strictly increasing sequence \$ a_i \$ such that \$ y_i = x_{a_i} \$
• Each character appears in \$ x \$ exactly twice as many times as it appears in \$ y \$

For example, "acb", "bac" and "bca" are all halves of "baccba", but "abc" and "ac" aren't.

Given a string with English a-z characters (you can choose if you want it lowercase or uppercase), which you are guaranteed all characters appear an even number of times in, output an arbitrary half of it.

Test Cases

"aaaabbbb" -> "aabb"
"abab" -> "ab", "ba"
"aabbaa" -> "aab", "aba", "baa"
"aabbaaaa" -> "aaba", "abaa", "baaa"
"baccba" -> "acb", "bac", "bca", "cba"
"aabbcc" -> "abc"
"abcabc" -> "abc", "acb", "bac", "bca", "cab"

Rules

• You can use any reasonable I/O format.
• You can print any half of it, or a list containing any non-empty subset of its halves, with or without duplicates.
• The distribution of the output can be whatever you want, as long as only valid outputs have a non-zero chance to be selected.
• Standard loopholes are disallowed.

This is code golf, so the shortest answer wins.

Answer 1

Python NumPy, 36 bytes

lambda s:s[sorted(s.argsort()[::2])]

Attempt This Online!

Takes and returns arrays of characters.

Answer 2

JavaScript (Node.js), 23 bytes

a=>a.filter(c=>a[c]^=1)

Try it online!

Answer 3

BQN, 6 bytes

⊢/˜2|⊒

Try it at BQN REPL

BQN's "Occurrence count" (⊒) operator, which returns a number for each element indicating how many previous elements match it, is pretty useful here.
Select elements from the input (⊢/˜) specified by the occurrence count of each of them (⊒) modulo 2 (2|).

Answer 4

Brachylog, 3 bytes

p~j

Try it online!

(jp with reversed I/O appears not to work.)

Originally, I had ⊇.jp?∧ (which can generate all halves, with an extreme volume of duplicates), but it turns out that the order in which p tries permutations maximizes the length of the prefix of items which are not rearranged. So:

p      Permute the input such that
 ~j    the output is a string which concatenated with itself is the input.

It appears that the output is guaranteed to be in a valid order because of this, but I'm not entirely sure--relevant source if anyone else wants to reason through it, or engineer a counterexample.

Answer 5

J, 11 bytes

#~2|1#.]=]\

Try it online!

• #~ Filter by
• 2|1#.]=]\ Prefixes where the count of items that equal the last item is odd.

Just noticed this is the same approach as the BQN answer, though this one I arrived at independently after waking up today.

port of loopy walt's answer, 14 bytes

{~[:/:~_2{.\/:

Try it online!

Port of loopy walt's excellent idea.

Answer 6

Vyxal, 8 bytes

ṗṠ'ds?s=

Try it Online!

Tack on a ;U if halves must be unique.

ṗṠ       # Subsequences as strings
  '      # Filtered by
   ds    # It doubled, sorted
       = # Equals...
     ?s  # The input sorted

Answer 7

Charcoal, 9 bytes

Φθ﹪№…θκι²

Try it online! Link is to verbose version of code. Explanation:

 θ          Input string
Φ           Filtered where
   №        Count of
       ι    Current character in
     θ      Input string
    …       Truncated to length
      κ     Current index
  ﹪     ²   Is odd

Answer 8

Jelly, 5 bytes

Ụm2Ṣị

Try it online! Or see the test suite.

How?

Same idea loopy walt had.

Ụm2Ṣị - Link: list, X
Ụ     - grade X up -> indices sorted by value
 m2   - mod2 slice -> 1st, 3rd, 5th, etc.
   Ṣ  - sort
    ị - index into X

Answer 9

Wolfram Language (Mathematica), 34 29 26 24 23 bytes

Select[g@#*=-1&]
_g=1>0

Try it online!

Input and output a list of characters. Keeps every other occurrence of each letter, starting from the second.

_g=1>0              per-character indicator
Select[        ]    keep in input where:
       g@#*=-1&       negate corresponding indicator
                      (-True is not truthy)
                    (all indicators receive an even # of negations,
                     so are reusable)

Answer 10

Perl 5 -p, 27 bytes

for$c(a..z){s/$c.*?\K$c//g}

Try it online!

Answer 11

Perl 5 + -lF -M5.10.0, 20 bytes

say grep++${$_}%2,@F

Try it online!

Answer 12

Vyxal, 5 bytes

⇧y_sİ

Try it Online!

Port of loopy walt's answer. I/O as list of chars.

⇧y_sİ
⇧     # Grade up
 y_   # Every other item starting from the first
   s  # Sort
    İ # Index into the input

y_ (uninterleave, pop) could alternatively be 2Ḟ (every 2nd item).

Answer 13

Retina 0.8.2, 34 bytes

(.)(?=(?(\1)((?<-3>)|()).|.)*$)\3

Try it online! Link includes test cases. Explanation:

(.)(?=

Capture a character, then looking ahead...

(?(\1)

... if the initial character appears, then...

((?<-3>)|())

... unset $3 if it's set, otherwise set it to the empty string...

.|.)*$)

... and check all the remaining characters in the string.

\3

If $3 is set at this point (i.e. has been toggled an odd number of times), then...

... delete the character.

Answer 14

lin, 40 bytes

.#n.n `pset"2rep.n \;.' eq"`#
.(""sort )

Try it here! Outputs an iterator of subsequences.

For testing purposes (use -i flag if running locally):

"abcabc" ; `_
.#n.n `pset"2rep.n \;.' eq"`#
.(""sort )

Explanation

Similar to @emanresu A's answer. Prettified code:

.#n .n `pset ( 2rep .n (.( ""sort )).' eq ) `#

• .#n input as n
• .n `pset powerset of n
• (...) `# filter each subsequence s...
  • 2rep repeat s
  • .n push n
  • (.( ""sort )).' sort s and n
  • eq check if equal

Answer 15

Curry (PAKCS), 28 bytes

f[]=[]
f(a:b++a:c)=a:f(b++c)

Try it online!

This may returns multiple results, with duplicates, but not necessarily all of them. If this is not allowed, you can add the flag :set +first to print only the first result: Try it online!.

Answer 16

Pyth, 7 bytes

q#.-QTy

Try it online!

Returns the half of the input which occurs last in the input, repeated for every time it appears as a subsequence of the input.

q#.-QTy
      y  subsequences of input
 #       filtered by
  .-QT   multiset difference with input
q        equals the subsequence

Answer 17

Jelly, 13 bytes

®;©ṛ
Ç®ċ%2
ÇƇ

Try it online!

® (load register)
 ; (concatenate with [tacit argument, character we're filtering])
  © (store result of previous link in register)
   ṛ (return right argument [tacit argument, character we're filtering])


Ç (previous link as a monad, [v=character, new_v=character])
 ®ċ (count occurrences of [character] in register)
 %2 (mod2 of [count])


Ç (previous link as monad, [v=character, new_v=1 or 0])
 Ƈ (filter all items, keeping all that satisfy condition, [v=argument])

Filter each character, storing them in a growing list of previous seen characters. Every time you see a character for an odd numbered time, keep it.

Answer 18

x86-64 machine code, 12 bytes

AC 84 C0 0F BB C2 77 01 AA 75 F5 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string; and the address of the input, as a null-terminated byte string, in RSI.

In assembly:

f:  lodsb           # Load a byte from the string into AL, advancing the pointer.
    test al, al     # Set flags based on that byte. In particular, ZF=1 iff it's 0.
    btc edx, eax    # Invert the bit in EDX indexed by the low 5 bits of that byte.
                    #  Set CF to the previous value of that bit. Leave ZF unchanged.
    ja s            # Jump if CF and ZF are both 0.
    stosb   # (If CF=1 or ZF=1) Add the byte to the output, advancing the pointer.
s:  jnz f           # Jump back, to repeat, if ZF is 0.
    ret             # Return.

Because EDX is not initialised, this can keep either the odd instances or the even instances of each letter; either possibility is acceptable. In the TIO demonstration, a RDRAND instruction is added to show multiple possibilities.

Answer 19

R, 24 bytes

\(x,`+`=order)x[!++x%%2]

Attempt This Online!

Answer 20

Octave / MATLAB, 31 30 bytes

@(s)s(j^2.^sum(triu(s==s'))>0)

Anonymous function that inputs and outputs character vectors.

The code keeps each character that has appeared an even number of times so far.

Try it online!

Answer 21

05AB1E, 7 bytes

ηε¤¢É}Ï

Outputs the first valid prefix.

Try it online or verify all test cases.

Or alternatively (port of @emanresuA's Vyxal answer):

æʒº{I{Q

Outputs a list of all valid results, with duplicates.

Try it online or verify all test cases.

Explanation:

η        # Get all prefixes of the (implicit) input-string
 ε   }   # Map each prefix to:
  ¤      #  Push its last character (without popping)
   ¢     #  Count how many times this character occurs
    É    #  Check if the count is odd
      Ï  # Keep all characters of the (implicit) input-string at the truthy indices
         # (after which this string is output implicitly)

æ        # Get the powerset of the (implicit) input-string
 ʒ       # Filter it by:
  º      #  Mirror it (to duplicate its characters)
   {     #  Sort its characters
      Q  #  Check if it's equal to
    I{   #  The input-string with sorted characters as well
         # (after which the filtered list is output implicitly)

Answer 22

Python 3, 46 45 bytes

-1 Thanks to @Command Master

f=lambda s:s and s[:s.count(s[0])%2]+f(s[1:])

Try it online!

Answer 23

Retina 0.8.2, 25 bytes

^
,
+`,(.)(.*)\1
$1,$2
,

Try it online! (Test harness borrowed from Neil's answer.)

Explanation

^
,

Insert a comma at the beginning of the string. (Any non-alphabetic delimiter will do.)

+`,(.)(.*)\1
$1,$2

Repeat until the regex no longer matches: Match the delimiter, the next character after it (group 1), any run of characters (group 2), and the character from group 1 again. Replace with the character from group 1, the delimiter, and group 2.

In effect: Comb through the string from left to right. On each iteration, move the first character to the output section, and delete another copy of that character from later in the string.

,

Remove the delimiter.

Answer 24

C (gcc), 70 67 bytes

• Saved three bytes thanks to ceilingcat: using K&R-style argument type declaration and a neat write.2 call to branch on printing a pointed-to character.

p[91];main(_,a)char**a;{for(++a;**a;++*a)write(1,*a,!(p[**a]^=1));}

Try it online!