Skip to main content
Code Golf

Return to Question

Became Hot Network Question
Added minor clarification to the test cases
Source Link
Kevin Cruijssen
Kevin Cruijssen
  • 131.5k
  • 13
  • 144
  • 384

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.

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

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.
deleted 1 character in body
Source Link
Command Master
Command Master
  • 10.7k
  • 1
  • 12
  • 73

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, more than one valid outputpermutation exist, and you may output any valid permutationone of them.

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

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.

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, 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.
Source Link
Command Master
Command Master
  • 10.7k
  • 1
  • 12
  • 73

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