Generate a permutation from the high-water marks code-golf permutations restricted-complexity open-ended-function

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 there isn't a single valid output, and you may output any 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.

Generate a permutation from the high-water marks

Generate a permutation from the high-water marks code-golf permutations restricted-complexity open-ended-function

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 polynomial time in \$n\$.

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

Test Cases

In all of those except the first there isn't a single valid output, and you may output any 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.

Generate a permutation from the high-water marks code-golf permutations restricted-complexity open-ended-function

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 there isn't a single valid output, and you may output any 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.

Generate a permutation from the high-water marks code-golf permutations restricted-complexity open-ended-function

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

Test Cases

In all of those except the first there isn't a single valid output, and you may output any 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.

Generate a permutation from the high-water marks code-golf permutations restricted-complexity open-ended-function

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 polynomial time in \$n\$.

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

Test Cases

In all of those except the first there isn't a single valid output, and you may output any 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.