Hide the buildings

Question

Shorter version of Skyscrapers Challenge

Task

Given an array of building heights and a positive integer k, find all the permutations(without duplicates) of the heights such that exactly k buildings are visible.

Any building will hide all shorter or equal height buildings behind it.

Any format for input and output is valid.

Input array will never be empty.

In case it is not possible to see exactly as many buildings, output anything that cannot be an answer but no error.

Examples:

(Length of output is shown for very long outputs,but your output should be all possible permutations)

input:[1,2,3,4,5],2
output: 50

input:[5,5,5,5,5,5,5,5],2
output: []

input:[1,2,2],2
output:[(1,2,2)]
Seeing from the left, exactly 2 buildings are visible.

input:[1,7,4],2
output:[(4, 7, 1), (1, 7, 4), (4, 1, 7)]

input:[1,2,3,4,5,6,7,8,9],4
output:67284

input:[34,55,11,22],1
output:[(55, 34, 11, 22), (55, 22, 34, 11), (55, 34, 22, 11), (55, 11, 34, 22), (55, 22, 11, 34), (55, 11, 22, 34)]

input:[3,4,1,2,3],2
output:31

This is code-golf so shortest code wins

Optional: If possible, can you add something like if length is greater than 20: print length else print answer. In the footer, not in the code.

Answer 1

05AB1E, 10 9 bytes

œÙʒη€àÙgQ

Try it online or verify (almost) all test cases (test case [1,2,3,4,5,6,7,8,9],4 times out).
Footer of the TIO does what OP asked at the bottom:

Optional: If possible, can you add something like if length is greater than 20: print length else print answer. In the footer, not in the code.

Explanation:

œ            # Permutations of the (implicit) input-list
             #  i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
 Ù           # Only leave the unique permutations
             #  i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
             #   → [[1,2,2],[2,1,2],[2,2,1]]
  ʒ          # Filter it by:
   η         #  Push the prefixes of the current permutation
             #   i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
    ۈ       #  Calculate the maximum of each permutation
             #   i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
      Ù      #  Only leave the unique maximums
             #   i.e. [1,2,2] → [1,2]
       g     #  And take the length
             #   i.e. [1,2] → 2
        Q    #  And only leave those equal to the second (implicit) input
             #   i.e. 2 and 2 → 1 (truthy)

Answer 2

Haskell, 73 bytes

import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations

Try it online!

Answer 3

Jelly, 12 10 bytes

Œ!Q»\QL=ʋƇ

Try it online!

-2 bytes by @Erik the Outgolfer

This is a dyadic function taking the building heights and k in that order.

Œ!                All permutations of first input
Œ!Q               Unique permutations of first input
   »\              Running maximum
     Q             Unique values
      L            Length of this array
       =           Equals k
        ʋ        Create a monad from these 4 links
   »\QL=ʋ        "Are exactly k buildings visible in arrangement x?"
         Ƈ     Filter if f(x)
Œ!Q»\QL=ʋƇ     All distinct perms of first input with k visible buildings.

Answer 4

Pyth, 18 16 bytes

fqvzl{meSd._T{.p

Try it here.

Note that the online version of the Pyth interpreter throws a memory error on the largest test case.

f                       Filter lambda T:
  q                       Are second input and # visible buildings equal?
    v z                     The second input value
    l {                     The number of unique elements in
        m                   the maximums
          e S d             ...
          ._ T              of prefixes of T
    { .p                  over unique permutations of (implicit first input)

Answer 5

Perl 6, 81 63 bytes

-18 bytes thanks to nwellnhof!

{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [\max] @_}}

Try it online!

Anonymous code block that takes input curried, e.g. f(n)(list). That .unique(:with(*eqv*)) is annoyingly long though :(

Explanation:

{;                                                            }  # Anonymous code block
  *.permutations.unique(:with(*eqv*))  # From all distinct permutations
                                     .grep:{                 }  # Filter where
                                                set [\max] @_   # Visible buildings
                                            $_==      # Equals num

Answer 6

Japt, 11 bytes

á f_åÔâ Ê¥V

Try it online!

For the longer outputs, adding } l to the end will output the length instead. The online interpreter times out for the [1,2,3,4,5,6,7,8,9],4 test case, regardless of outputting the length or the list.

Explanation:

á              :Get all permutations
  f_           :Keep only ones where:
    åÔ         : Get the cumulative maximums (i.e. the visible buildings)
      â Ê      : Count the number of unique items
         ¥V    : True if it's the requested number

Answer 7

JavaScript (ES6), 108 107 bytes

Takes input as (k)(array). Prints the results with alert().

k=>P=(a,p=[],n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)

Try it online!

Commented

k =>                        // k = target number of visible buildings
  P = (                     // P = recursive function taking:
    a,                      //   a[] = list of building heights
    p = [],                 //   p[] = current permutation
    n = k,                  //   n = counter initialized to k
    h = 0                   //   h = height of the highest building so far
  ) =>                      //
    a.map((v, i) =>         // for each value v at position i in a[]:
      P(                    //   do a recursive call:
        a.filter(_ => i--), //     using a copy of a[] without the i-th element
        [...p, v],          //     append v to p[]
        n - (v > h),        //     decrement n if v is greater than h
        v > h ? v : h       //     update h to max(h, v)
      )                     //   end of recursive call
    )                       // end of map()
    + a ||                  // unless a[] was not empty,
    n ||                    // or n is not equal to 0,
    P[p] ||                 // or p[] was already printed,
    alert(P[p] = p)         // print p[] and store it in P

Answer 8

Python 2, 114 113 bytes

lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*

Try it online!

_{-1 byte, thanks to ovs}

---

Python 3, 113 bytes

lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*

Try it online!

Answer 9

J, 43 38 bytes

-5 bytes after incorporating an optimization from Kevin's O5AB13 answer

(]#~[=([:#@~.>./\)"1@])[:~.i.@!@#@]A.]

Try it online!

ungolfed

(] #~ [ = ([: #@~. >./\)"1@]) ([: ~. i.@!@#@] A. ])

explanation

we're merely listing all possible perms i.@!@#@] A. ], taking uniq items thereof with ~., then filtering those by the number of visible building, which must equal the left input.

the key logic is in the parenthetical verb which calcs the number of visible buildings:

([: #@~. >./\)

Here we use a max scan >./\ to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.