13
\$\begingroup\$

Given a permutation, we can define its high-water marks as the indices in which its cumulative maximum increases, or, equivalently, indices with values bigger than all previous values.

For example, the permutation \$ 4, 2, 3, 7, 8, 5, 6, 1 \$, with a cumulative maximum of \$ 4, 4, 4, 7, 8, 8, 8, 8 \$ has \$1, 4, 5\$ as (1-indexed) high-water marks, corresponding to the values \$4, 7, 8\$.

Given a list of indices and a number \$n\$, generate some permutation of size \$n\$ with the list as its high-water marks in time polynomial in \$n\$.

This is code golf, so the shortest solution in each language wins.

Test Cases

In all of those except the first, more than one valid permutation exist, and you may output any one of them.

1-based high-water mark indices, n -> a valid permutation

[1, 2, 3], 3 -> [1, 2, 3]
[1, 2, 3], 5 -> [2, 3, 5, 4, 1]
[1, 4, 5], 8 -> [4, 2, 3, 7, 8, 5, 6, 1]
[1], 5 -> [5, 4, 3, 2, 1]
[1, 5], 6 -> [4, 1, 3, 2, 6, 5]

Rules

  • You can use any reasonable I/O format. In particular, you can choose:
    • To take the input list as a bitmask of size \$n\$, and if you do that whether to take the size at all.
    • Whether the input is 0-indexed or 1-indexed.
    • Whether to have the first index (which is always a high-water mark) in the input. When taking a bitmask, you may take a bitmask of size \$n-1\$ without the first value. When taking a list of indices, you can have it indexed ignoring the first value.
    • Whether the output is a permutation of the values \$0,1,...,n-1\$ or \$1,2,...,n\$.
    • To output any non-empty set of the permutations, as long as the first permutation is outputted in polynomial time.
    • To have the cumulative minimum decrease in the given points instead.
    • To have the cumulative operation work right-to-left, instead of left-to-right.
  • It is allowed for your algorithm to be non-deterministic, as long as it outputs a valid permutation with probability 1 and there's a polynomial \$p(n)\$ such that the probability it takes more than \$p(n)\$ time to run is negligible. The particular distribution doesn't matter.
  • Standard loopholes are disallowed.
\$\endgroup\$
5
  • \$\begingroup\$ I'm genuinely confused by this... what does it mean by "in time polynomial in n" and why is the second test case different from the first (other than the length) \$\endgroup\$ Feb 27, 2023 at 16:34
  • \$\begingroup\$ @12944qwerty "in time polynomial in n" means that there must exist some polynomial such that the time your program takes to execute is bounded by \$p(n)\$ for any input with size \$n\$. Practically, it means you can't do stuff like test all possible permutations. What do you mean by why is the second test case different form the first? [1, 2, 3, 4, 5] wouldn't be a valid answer to it, because it has all indices as high-water marks, and not only the first 3. \$\endgroup\$ Feb 27, 2023 at 16:37
  • 3
    \$\begingroup\$ Brownie points for an answer that actually makes use of the probability clause. \$\endgroup\$
    – xigoi
    Feb 27, 2023 at 17:51
  • \$\begingroup\$ Will the list contains duplicate numbers? \$\endgroup\$
    – tsh
    Feb 28, 2023 at 2:29
  • \$\begingroup\$ @tsh no, and you can assume whether it's increasing/decreasing \$\endgroup\$ Feb 28, 2023 at 3:22

14 Answers 14

9
\$\begingroup\$

Nibbles, 5 bytes

.,@?:-,_@@

Attempt This Online!

Puts the \$k\$ highest numbers at the specified indices in ascending order and the remaining numbers at the remaining indices, where \$k\$ is the number of marks.

[1, 4, 5], 8 -> [6, 1, 2, 7, 8, 3, 4, 5]

Explanation

.,@?:-,_@@
.          Map
 ,          range
  @          second input
   ?        find index in
    :        join
     -        list difference
      ,        range
       _        second input
        @      first input
         @    first input

If I'm reasoning correctly, the time complexity should be \$\mathcal O\left(n^2\right)\$.

\$\endgroup\$
6
\$\begingroup\$

R, 23 bytes

Edit: -9 bytes thanks to Command Master by switching to use a bitmask as input

function(h)rank(h,,"f")

Try it online!

Input is simply a bitmask h, no need to provide n as this is implicitly the length of the bitmask.
The "f" (short for ties="first") argument to rank() indicates that ties with the same rank should be broken using "increasing values at each index set of ties".

R, 32 bytes

function(h,n)rank(1:n%in%h,,"f")

Try it online!

Same approach as above, except inputting h as the indices of high-water marks, together with n. 1:n %in% h returns a vector of mainly zeros, with ones where the high-water marks should be (in other words, converting the indices to a bitmask).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ function(h,n){x=1:n;x[h]=n*2:n;rank(x)} seems to work for -1 \$\endgroup\$ Feb 27, 2023 at 17:06
  • 1
    \$\begingroup\$ 38 bytes \$\endgroup\$
    – Giuseppe
    Feb 27, 2023 at 17:09
  • 2
    \$\begingroup\$ If you take a bitmask couldn't you replace 1:n%in%h with h and not take n? \$\endgroup\$ Feb 28, 2023 at 9:42
  • \$\begingroup\$ @CommandMaster - yes, thanks! I hadn't noticed the generous input allowances! \$\endgroup\$ Feb 28, 2023 at 10:39
6
\$\begingroup\$

Jelly,  4  2 bytes

ỤỤ

A monadic Link that accepts a bitmask identifying the high watermarks and yields a permutation.

Try it online! Or see the test-suite.

How?

ỤỤ - Link: bitmask                        e.g. [1,0,0,1,0,0]
Ụ  - grade-up (indices of sorted values)       [2,3,5,6,1,4]   
 Ụ - grade-up (indices of sorted values)       [5,1,2,6,3,4]

Previous at 4 bytes (not using a bitmask):

ReÞỤ

A dyadic Link that accepts the number on the left and the high watermark indices on the right and yields a permutation.

Try it online! Or see the test-suite.

How?

ReÞỤ - Link: n; I                       e.g. n=6; I=[1,4]
R    - range (n)                             [1,2,3,4,5,6]
  Þ  - sort by:
 e   -   exists in (I)?                      [2,3,5,6,1,4]
   Ụ - grade-up (indices of sorted values)   [5,1,2,6,3,4] 
\$\endgroup\$
4
\$\begingroup\$

Vyxal, 6 bytes

ɾ$ÞṖRf

Try it Online!

Takes n and then a list of indices.

ɾ      # range
 $     # swap top two items on the stack
  ÞṖ   # split before indices
    R  # reverse each
     f # flatten
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 8 bytes

LDŠåÅ¡í˜

Port of @AndrovT's Vyxal answer.

Try it online or verify all test cases.

Explanation:

L         # Push a list in the range [1, first (implicit) input n]
 D        # Duplicate this list
  Š       # Triple-swap it with the second (implicit) input: [1,n], input-list, [1,n]
   å      # Check for each value of [1,n] whether it's in the input-list
    Å¡    # Split the second [1,n]-list before the truthy indices
      í   # Reverse each inner list
       ˜  # Flatten it to a single list
          # (after which the result is output implicitly)
\$\endgroup\$
2
  • \$\begingroup\$ Your TIO link somehow got replaced with the language link. \$\endgroup\$
    – xigoi
    Feb 27, 2023 at 20:36
  • \$\begingroup\$ @xigoi Woops, thanks for noticing. Should be fixed now. \$\endgroup\$ Feb 28, 2023 at 7:37
2
\$\begingroup\$

Pyth, 10 bytes

XKSE+-KQQK

Try it online!

Takes the indices then the length, runs in \$\mathcal{O}(n^2)\$. Uses the same general strategy as most others, putting the \$n\$ highest values at the given indices.

Explanation

              # implicitly assign Q = eval(input()) to the indices
 KSE          # assign K = [1, 2, ..., eval(input())]
     -KQ      # elements of K not in Q
    +   Q     # concatenated to Q
XK       K    # translate K from this to K
\$\endgroup\$
2
\$\begingroup\$

R, 16 bytes

Not enough reputation to comment on Dominic's answer, but using the new anonymous function syntax in R, a few bytes can be shaved off:

\(h)rank(h,,"f")

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf! I'm sure Dominic is aware of the new function syntax, but Try It Online (TIO) is still using 3.6, and its maintainer has, unfortunately, taken a leave of absence from CGCC, so it's not likely to get updated. There are alternatives, e.g., Attempt This Online (aka ATO) with 4.0+ installed, but sometimes I still find myself defaulting to use TIO instead. At any rate, I've upvoted and hope you enjoy your time golfing! \$\endgroup\$
    – Giuseppe
    Feb 28, 2023 at 15:58
  • \$\begingroup\$ +1 from me, too. Giuseppe is right that I knew the \ syntax, but it's a valid improvement to use it. \$\endgroup\$ Mar 7, 2023 at 20:34
1
\$\begingroup\$

Python 3, 64 bytes

Uses zero-based indexing

f=lambda m,n:sum(([*range(*t)][::-1]for t in zip(m,m[1:]+[n])),[])
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You can drop the f= since it's not recursive. Also, list(range(*t)) can be [*range(*t)] \$\endgroup\$
    – The Thonnu
    Feb 27, 2023 at 17:27
  • \$\begingroup\$ 58 bytes \$\endgroup\$ Feb 27, 2023 at 17:54
  • \$\begingroup\$ Your output contains \$n-1\$ elements, not \$n\$ elements. Maybe you want f=lambda m,n:sum(([*range(*t)][::-1]for t in zip([0]+m,m+[n])),[]) instead. \$\endgroup\$
    – tsh
    Feb 28, 2023 at 3:11
  • \$\begingroup\$ Based on comment by @97.100.97.109, this is 55 bytes in Python 2: lambda m,n:sum(map(range,m+[n],[0]+m,[-1]*-~len(m)),[]) \$\endgroup\$
    – tsh
    Feb 28, 2023 at 3:27
  • \$\begingroup\$ @tsh I think it's fine. Zero must be in the input anyway. \$\endgroup\$ Feb 28, 2023 at 9:43
1
\$\begingroup\$

JavaScript (Node.js), 45 bytes

m=>n=>m.map(i=>i?++n-eval(m.join`+`):++x,x=0)

Attempt This Online!

Takes a bit mask and length. Runs in \$\mathcal O(n)\$.

This is probably my first time golfing in JavaScript, please leave suggestions how to improve the code.

-7 thanks to Kevin Cruijssen, Shaggy and Arnauld

\$\endgroup\$
4
  • 1
    \$\begingroup\$ m.reduce((a,b)=>a+b) can be eval(m.join`+`) for -5 bytes. \$\endgroup\$ Feb 27, 2023 at 17:54
  • 1
    \$\begingroup\$ @KevinCruijssen So dirty, I love it! Thanks! \$\endgroup\$
    – xigoi
    Feb 27, 2023 at 17:58
  • 1
    \$\begingroup\$ Save a byte with currying \$\endgroup\$
    – Shaggy
    Feb 27, 2023 at 19:00
  • 1
    \$\begingroup\$ 45 bytes (including currying syntax, as already suggested by Shaggy) \$\endgroup\$
    – Arnauld
    Feb 27, 2023 at 20:29
1
\$\begingroup\$

Retina, 38 bytes

^.+
*
_
$.`¶
^D`
G`.
.+
$&,$:&
N`
.+,

Try it online! Takes n as the first input and then the element of the 0-indexed list. Explanation: Inspired by @DominicVanEssen's R answer.

^.+
*

Convert n to unary.

_
$.`¶

Get a range from 0 to n.

^D`

Remove all but the last instance of all duplicates.

G`.

Remove all blank lines.

.+
$&,$:&

Append the line index to each value.

N`

Sort by value.

.+,

Delete the values, leaving their original indices.

\$\endgroup\$
0
\$\begingroup\$

Python NumPy, 56 bytes

def f(m,n):x=m[:1]*range(n);_,*x[m-1]=*x[m-1],n;return x

Attempt This Online!

1-based. Expects a numpy array and an integer.

How?

Populates the output with a 0-based (!) range. Then shifts the values at the marked indices one position to the left ignoring non marked indices and filling the right most position with n. As the left most marked index always is 0, a 0 was lost and an n gained, generating a 1-based permutation.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 12 bytes

IEη⌕⁺⁻…⁰ηθθι

Try it online! Link is to verbose version of code. 0-indexed. Explanation: Port of @xigoi's Nibbles answer.

  η             Input `n`
 E              Map over implicit range
   ⌕            Find index of
           ι    Current value in
      …         Range from
       ⁰        Literal integer `0`
        η       To input `n`
     ⁻          Remove elements from
         θ      Input list
    ⁺           Concatenated with
          θ     Input list
I               Cast to string
                Implicitly print
\$\endgroup\$
0
\$\begingroup\$

Japt, 11 10 bytes

õ ò@VøYÃcÔ

Try it

-1 by Shaggy (crossed out 11 is still regular 11)

õ ò@VøYÃcÔ 
õ          # range [1, input integer]
  ò@   Ã   # partitioned between pairs X, Y where
    VøY    #   Y is contained in input array
        cÔ # reverse each and flatten
\$\endgroup\$
1
  • \$\begingroup\$ ò1 can be õ here. \$\endgroup\$
    – Shaggy
    Mar 6, 2023 at 12:48
0
\$\begingroup\$

JavaScript (Node.js), 39 bytes

x=>x.map(t=>!t&&++i,i=0).map(t=>t||++i)

Try it online!

Take marks

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.