Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- KX Community
- :
- Discussion Forums
- :
- kdb+ and q
- :
- One hundred prisoners

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

One hundred prisoners

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.06 02:34 AM

The One Hundred Prisoners problem has a famously counter-intuitive solution, nicely explained on YouTube:

https://www.youtube.com/watch?v=iSNsgj1OCLA

Exploring it in q is illuminating!

George Berkeley kicked this off in the Vector Dōjō :

A problem I found interesting, and maybe you will too...You can view a vector`v = (1 0 2 3 5 6 4)`

as a permutation, i.e. given an index`i`

, the permutation sends`i`

to`v[i]`

. If we apply the permutation multiple times, then eventually we end up where we started. In fact, if we look at`v`

, we can see it breaks down into the following cycles:0 -> 1 -> 0 2 -> 2 3 -> 3 4 -> 5 -> 6 -> 4Given a permutation, return the number of cycles! (so 4 for the given`v`

)

```
q)v:1 0 2 3 5 6 4
q)v scan 0
0 1
q)(v scan)each 0 2 3 4
0 1
,2
,3
4 5 6
```

Each item belongs to one and only one cycle. Above, we see all the items, so we see there are only four cycles. A more brute-force approach:

```
q)(v scan)each v
1 0
0 1
,2
,3
5 6 4
6 4 5
4 5 6
```

`0 1`

and `1 0`

are the same cycle. Sorting each cycle lets us remove duplicates and count.```
q)distinct(asc v scan)each v
`s#0 1
`s#,2
`s#,3
`s#4 5 6
q)count distinct(asc v scan)each v
4
```

Rian Ó Cuinnegáin linked the problem to the One Hundred Prisoners problem. The key to the problem (spoiler) is that in 100-item permutations, there is about a one-in-three chance that the maximum cycle length is no more than 50. (Above, it is 3.)

```
q)max(count v scan)each v
3
q)max{(count x scan)each x} -100?100
44
q)max{(count x scan)each x} -100?100
55
q)max{(count x scan)each x} -100?100
90
```

This could be smarter. Consider the last case. The longest cycle has 90 items. Once it is found, we have the cycle length for all 90 of its items. We no longer need to evaluate the other 89.

Let’s work on a state with three items: the cycle length for each index, the permutation itself, and the untested indices.

```
q)show q:-10?10 / test
5 0 1 9 2 6 8 4 7 3
q)is:(#[;0]count@;::;til count@)@\: / initial state
q)is q
0 0 0 0 0 0 0 0 0 0
5 0 1 9 2 6 8 4 7 3
0 1 2 3 4 5 6 7 8 9
```

Now a step function that updates the state by evaluating the next index.

```
q)step:{[c;p;i] if[count i;c[r]:count r:p scan i 0];(c;p;where not c)} .
q)step is q
8 8 8 0 8 8 8 8 8 0
5 0 1 9 2 6 8 4 7 3
3 9
```

Above, the cycle of which 0 is a member has length 8. After the first step, only two indices remain to evaluate.

So much less work to do:

```
q)p:-100?100
q)\t:1000 max(count p scan)each p
134
q)\t:1000 max first step over is p
13
```

This approach also quickly gives us the answer to the question George first posed: how many cycles are in the permutation? The first item of a scan result is of course the initial state; we count the rest.

```
q)-1+ count step scan is v
4
q)-1+ count step scan is p
6
```

My thanks to Vector Dōjō tutors Rian Ó Cuinnegáin and Cillian Murphy for their work on this.

The Vector Dōjō will meet again online soon. In the meantime, members fool around with problems like these in the Iverson College workspace on Slack. (DM me at sjt@5jt.com for an invitation.)

1 REPLY 1

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.06 11:29 AM

Brilliant content @SJT

Here's to many more Vector Dōjō events in the future!

Kudos to all involved 👏

Related Content

Main Office Contacts

**EMEA**

Tel: +44 (0)28 3025 2242

**AMERICAS**

Tel: +1 (212) 447 6700

**APAC**

Tel: +61 (0)2 9236 5700

Useful Information

Popular Links

Follow Us

KX. All Rights Reserved.

KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.