# Generate a permutation from the high-water marks

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.
• 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) Feb 27 at 16:34
• @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. Feb 27 at 16:37
• Brownie points for an answer that actually makes use of the probability clause. Feb 27 at 17:51
• Will the list contains duplicate numbers?
– tsh
Feb 28 at 2:29
• @tsh no, and you can assume whether it's increasing/decreasing Feb 28 at 3:22

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

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

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

# 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


# 05AB1E, 8 bytes

LDŠåÅ¡í˜


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)

• @xigoi Woops, thanks for noticing. Should be fixed now. Feb 28 at 7:37

# Jelly,  4  2 bytes

ỤỤ


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]


# 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


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

• 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! Feb 28 at 15:58
• +1 from me, too. Giuseppe is right that I knew the \ syntax, but it's a valid improvement to use it. Mar 7 at 20:34

# Python 3, 64 bytes

Uses zero-based indexing

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

• You can drop the f= since it's not recursive. Also, list(range(*t)) can be [*range(*t)] Feb 27 at 17:27
• 58 bytes Feb 27 at 17:54
• 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.
– tsh
Feb 28 at 3:11
• 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)),[])
– tsh
Feb 28 at 3:27
• @tsh I think it's fine. Zero must be in the input anyway. Feb 28 at 9:43

# 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

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

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

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

# 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


# 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

• ò1 can be õ here. Mar 6 at 12:48
• @Shaggy I’ll never be good enough for you, will I? Thanks, I realized what the difference between the different range built-ins was the day after posting this but forgot to update the answer Mar 6 at 12:51