A permutation is a particular ordering of some list of objects. Problems tagged with permutation usually involve finding or generating permutations.
18
votes
11answers
1k views
All possible ways to interleave two strings
I recently saw this question on stackoverflow. It's a great question, but there's one fatal problem with the question. They are asking for the best way to do it. E.g, easiest to read, most idiomatic, ...
16
votes
24answers
2k views
Random array without repetition
I was answering one challenge here and this task was part of the challenge. I've got a 73 bytes solution in javascript. But I think it is too much for a simple thing.
Challenge
Given as input two ...
19
votes
3answers
302 views
Permutation Square Root
In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list:
2 1 4 3
represents the permutation σ such that σ(1) = 2, σ(2) = 1, σ(3) = 4, and σ(4) = 3.
...
-1
votes
0answers
49 views
combinations of characters [duplicate]
Write a function that takes two arguments, len (an int) and chars (a list). It should output a list of all the possible combinations of length len of items in the chars list, with repetition allowed.
...
17
votes
11answers
475 views
Maximise the squared difference
Consider a permutation of the integer values from 1 to N. E.g. this example for N = 4:
[1, 3, 4, 2]
We'll consider this list to be cyclic, such that 1 and 2 are treated as adjacent. One quantity we ...
20
votes
17answers
996 views
Rearranging the sequence
Introduction
Let's observe the following sequence (non-negative integers):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
For example, let's take the first three numbers. These are 0, 1, 2. ...
16
votes
8answers
601 views
Spiral Permutation Sequence
We can roll up the natural numbers in a rectangular spiral:
17--16--15--14--13
| |
18 5---4---3 12
| | | |
19 6 1---2 11
| | |
20 7---8---9--10
...
10
votes
2answers
179 views
The absent-minded linguist
Background
Your friend, a linguist, has recorded and analyzed some simple conversation snippets in various languages.
Being quite absent-minded, they have forgotten which language each snippet was ...
13
votes
6answers
442 views
Letters, Get Moving! Pt. 2
The first Letters, Get Moving! was very popular, but had limited participation. This one will be easier to solve, but hopefully involve some tricks in golfing.
You are given a string of only ...
14
votes
2answers
214 views
Can the Array be Unshuffled?
Background
Very skilled card handlers are capable of a technique whereby they cut a deck perfectly in half, then perfectly interleave the cards. If they start with a sorted deck and perform this ...
17
votes
1answer
356 views
Random Golf of the Day #6: Roll a d20
About the Series
First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You ...
16
votes
6answers
359 views
Find maximal matching in divisibility relation
You are given a set of positive integers. You must arrange them into pairs such that:
Each pair contains 2 numbers, one of which is a multiple of another. For example, 8 is a multiple of 4, and 9 is ...
9
votes
4answers
247 views
Rearrangement Inequality
Background
The Rearrangement Inequality is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x0, x1, x2...xn-1 and y0, y1, y2...yn-1 of the same ...
12
votes
8answers
469 views
Typesetting multidimensional labels
In a steam-punk multidimensional world, our boss wants to affix printed index labels to each drawer in our conglomerate's multidimensional file cabinet.
The boss wants to typeset the entire label ...
17
votes
14answers
656 views
Fun With Permutations
Who doesn't absolutely love permutations, right? I know, they are amazing––so much fun!
Well, why not take this fun and make it funner?
Here's the challenge:
Given an input in the exact form: nPr, ...
24
votes
19answers
2k views
Imitate an ordering
Given two lists of numbers, a source and a pattern, reorder the source to match the relative ordering of the pattern. Any two entries of the reordered source should compare the same way as the entries ...
16
votes
2answers
555 views
The Combinatorics of Transistor
The video game Transistor features a very interesting ability system. You collect 16 "Functions" which you can use in 16 different slots. What's interesting is that there are 3 types of slots and ...
11
votes
3answers
333 views
Possible Tetris sequences
Write code to figure out whether a run of Tetris pieces could be generated by the official Tetris algorithm. Fewest bytes wins.
Official Tetris games generate the sequence of falling pieces in a ...
31
votes
6answers
1k views
Can you reach this number by doubling and rearranging?
Inspired by this question on Math.SE.
Starting with 1 you can repeatedly perform one of the following two operations:
Double the number.
or
Rearrange its digits in any way you want, except that ...
9
votes
5answers
471 views
Cycle lengths for Perfect shuffles of decks of any size
Challenge
In the shortest amount of code:
Compute the length of the permutation cycle of a perfect shuffle on a deck of cards of any size n (where n ≥ 2 and n is even).
Output a table of all cycle ...
14
votes
8answers
867 views
Alphabetic Fannkuch
Fannkuch is a classic benchmark program. The name comes from the German "Pfannkuchen"- pancakes- for the algorithm's resemblance to flipping stacks of pancakes. A Fannkuch sequence of numbers is ...
16
votes
8answers
924 views
Every Possible Cycle Length
A function (or program) which takes inputs and provides outputs can be said to have a cycle if calling the function on its own output repeatedly eventually reaches the original number. For instance, ...
13
votes
5answers
378 views
Permutations of the Fifteen Puzzle
The Challenge
Consider the following diagram of the Fifteen Puzzle in its solved state:
_____________________
| | | | |
| 1 | 2 | 3 | 4 |
|____|____|____|____|
| | | | |
...
7
votes
3answers
252 views
Number of ways to sum [1..n] with [n+1..2n] such that each sum is prime
Let n > 0. Let X = [1..n] and Y = [n+1 .. 2n]. Define a(n) as the number of permutations p of Y such that every element of X + p(Y) is prime. For example:
n = 2
X = [1,2]
Y = [3,4]
p0(Y) = [3,4] ...
5
votes
1answer
187 views
Plus one sheep minus one sheep
Once upon a time long long ago...when there was no money or stocks yet, people were trading sheep. Even before (but close to) the invention of abacus, the great-grandfather of Warren Buffet decided it ...
14
votes
4answers
423 views
Order 40 sticks
We have 40 sticks of same widths but different heights. How many arrangements are there possible to put them next to each other so that when we look from right we see 10 sticks and when we look from ...
10
votes
3answers
561 views
Count the number of Hankelable matrices
Background
A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1s. E.g. a 5x5 binary Hankel matrix looks like
a b c d e
b c d e f
c d ...
16
votes
3answers
736 views
Reconstruct a Permutation
Introduction
Suppose that you are handed a random permutation of n objects.
The permutation is sealed in a box, so you have no idea which of the n! possible ones it is.
If you managed to apply the ...
11
votes
1answer
277 views
Constructing an Orthogonal-Diagonal Greco-Latin Square
Consider a grid of NxN unique elements. Each element has a letter (from A to the Nth letter, inclusive) and a number (from 1 to N, inclusive). Hence, each number/letter pair is in the grid exactly ...
39
votes
19answers
5k views
Shotgun Numbers
The Shotgun numbers are a sequence with a rather simple definition but some interesting structure. Start with the natural numbers:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...
9
votes
5answers
396 views
Total number of topological sorts
For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation.
Your task is ...
27
votes
33answers
5k views
Random Golf of the Day #1: Shuffle an Array
About the Series
I will be running a little series of code-golf challenges revolving around the theme of randomness. This will basically be a 9-Hole Golf Course, but spread out over several ...
16
votes
7answers
1k views
Typing with scrambled keys
Your friend isn't too good with computers so as a practical joke someone scrambled the letters (a-z) on his keyboard. When he sit down and tried to type his name looking at the keyboard he realized ...
7
votes
4answers
515 views
Curator's Dilemma
Introduction
You are a friend of a curator for an art museum, who has had the recent delight of getting modern art from four artists (some of which may give the curator zero pieces of art, young ...
22
votes
5answers
2k views
Sort a List With Swaps and Pops
Consider a randomized list of the integers 1 to N. You want to sort it using only the following actions:
Swap the first and last list elements. (S)
Pop off the first element and append it to the end ...
12
votes
2answers
2k views
Solve the (Rubiks) Pocket Cube
Your task
.. is to do what Brian Fantana apparently couldn't do, and solve the 2x2x2 Rubik's Cube.
The Layout
- - A B - - - -
- - C D - - - -
E F G H I J K L
M N O P Q R ...
20
votes
5answers
779 views
Draw a Permutation Path
Imagine the following diagrams as sets of vertical criss-crossing tubes.
1 2 1 2 1 2 3 4
\ / \ / \ / \ /
X | | |
/ \ / \ / \ / \
2 1 1 2 | X |
\ ...
7
votes
5answers
535 views
Permutation Numbering
The Challenge
For a given set of n integers, write a program which will output its lexicographic index.
The Rules
The input must only be a set of unique non-negative integers separated by spaces.
...
65
votes
11answers
10k views
The 9 Billion Names of God
The 9 Billion Names of God is a short story by Arthur C. Clarke. It's about a group of Tibetan monks whose order is devoted to writing down all the possible names of God, written in their own ...
3
votes
3answers
352 views
Find the next subpermutation of base-64 digits
Permutations of a set have a natural order called lexicographic order in which two permutations are compared by comparing the first position at which they differ. For the purposes of this question ...
3
votes
4answers
1k views
Obtaining ordering of cards [closed]
You are given a deck containing n cards. While holding the deck:
Take the top card off the deck and set it on the table
Take the next card off the top and put it on the bottom of the deck in your ...
15
votes
18answers
1k views
Code-Golf: Permutations
Write a function that takes as input a set of integers (can be a list, array or any other container with distinct numbers), and outputs the list of all its permutations.
Python (95 chars):
p=lambda ...
14
votes
6answers
1k views
Decompose a permutation into cycles
There is a well-known theorem that any permutation can be decomposed into a set of cycles. Your job is to write the shortest possible program to do so.
Input:
Two lines. The first contains a ...
10
votes
3answers
364 views
Permutation group operation
There is a well-known bijection between the permutations of n elements and the numbers 0 to n!-1 such that the lexicographic ordering of the permutations and the corresponding numbers is the same. For ...
