Questions tagged [permutations]

A permutation is a particular ordering of some list of objects. Problems tagged with permutation usually involve finding or generating permutations, including anagrams of text.

Filter by
Sorted by
Tagged with
31
votes
20answers
2k views

Faro shuffle an array

A Faro shuffle is a technique frequently used by magicians to "shuffle" a deck. To perform a Faro shuffle you first cut the deck into 2 equal halves then you interleave the two halves. For example <...
11
votes
7answers
510 views

Find a function with cycles of every length

A function is said to have a cycle of length n if there exists an x in its domain such that fn(x) = x and fm(x) ≠ x for 0 < m < n, where the superscript n denotes n-fold application of f. Note ...
12
votes
2answers
262 views

Rotation-safe Latin squares

A Latin square is a square that has no repeated symbols in either the X or Y columns. For example: ABCD DABC CDAB BCDA is one such square. Notice how every ...
12
votes
10answers
796 views

Permutations with Indistinguishable Items

Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each ...
13
votes
6answers
784 views

Magic number of a given length

Your program must take an input (n for the purpose of description) and output all permutations of a number that is n digits long ...
21
votes
12answers
2k 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 ...
13
votes
8answers
1k views

Parity of a Permutation

Background The parity of a permutation, as defined by wikipedia, is as follows: The sign or signature of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd. ...
20
votes
3answers
388 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,...
35
votes
32answers
2k views

Manage Trash So

It's become somewhat of a tradition in PPCG that some users temporarily change their names by an anagram (a new name formed by reordering the letters of the old). Sometimes it gets difficult to find ...
19
votes
11answers
614 views

Maximise the squared difference

Consider a permutation of the integer values from 1 to N. E.g. this example for N = 4: <...
20
votes
19answers
1k 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 ...
17
votes
8answers
752 views

Spiral Permutation Sequence

We can roll up the natural numbers in a rectangular spiral: ...
10
votes
2answers
244 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 in....
14
votes
6answers
588 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 ...
15
votes
2answers
303 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
2answers
920 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
387 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 ...
10
votes
4answers
297 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
499 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
838 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: ...
24
votes
20answers
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 ...
14
votes
17answers
942 views

Code Golf: Forwards sdrawkcaB sdrawkcaB Forwards Forwards sdrawkcaB

Task The user inputs a sentence - words only. Any input other than letters or spaces, including integers and punctuation, should throw an exception: "Sentence must only use letters". The output has a ...
20
votes
2answers
1k 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
426 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 ...
33
votes
6answers
2k 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 ...
10
votes
5answers
610 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
979 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 ...
21
votes
13answers
1k 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
406 views

Permutations of the Fifteen Puzzle

The Challenge Consider the following diagram of the Fifteen Puzzle in its solved state: ...
7
votes
3answers
285 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 ...
3
votes
1answer
349 views

Plus one sheep minus one sheep [closed]

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 ...
8
votes
7answers
342 views

Detecting anagrams within a Parent String

Given two strings, a parent string and a query string respectively, your task is to determine how many times the query string, or an anagram of the query string; appears in the parent string, in a ...
15
votes
4answers
447 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 ...
12
votes
3answers
625 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 1...
16
votes
3answers
843 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 ...
11
votes
1answer
681 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,...
45
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: ...
10
votes
5answers
499 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 ...
20
votes
3answers
1k views

Anagramming Stack Exchange question titles into programs

Stack Exchange currently has 134 question and answer sites. This includes all beta sites (such as PPCG) but not Area 51 proposals nor any meta sites, except for the "mother meta". To answer this ...
35
votes
35answers
6k 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 questions....
16
votes
7answers
2k 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 ...
-2
votes
2answers
883 views

Find Anagrams in the Dictionary [closed]

This a code challenge. The winner will be the person to provide the most efficient implementation of the solution in terms of algorithmic complexity. Using the dictionary found in '/usr/share/dict' (...
9
votes
4answers
556 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
7k 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 ...
6
votes
4answers
727 views

Find imperfect anagrams

The goal of this challenge is to write a program which takes a string (of any length) as input and displays anagrams (see these examples of anagrams) of this string, made by taking words in a ...
16
votes
2answers
4k 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 ...
20
votes
5answers
916 views

Draw a Permutation Path

Imagine the following diagrams as sets of vertical criss-crossing tubes. ...
9
votes
6answers
794 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. ...
74
votes
11answers
11k 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 alphabet....