Generate a permutation from the high-water marks

Question

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.

Answer 1

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)\$.

Answer 2

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

Answer 3

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] 

Answer 4

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

Answer 5

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)

Answer 6

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

Answer 7

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")

Answer 8

Python 3, 64 bytes

Uses zero-based indexing

f=lambda m,n:sum(([*range(*t)][::-1]for t in zip(m,m[1:]+[n])),[])

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

Charcoal, 12 bytes

ＩＥη⌕⁺⁻…⁰ηθθι

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

  η             Input `n`
 Ｅ              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
Ｉ               Cast to string
                Implicitly print

Answer 13

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

Answer 14

JavaScript (Node.js), 39 bytes

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

Try it online!

Take marks