[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: puzzle with string permutations [photo]
From: |
Yuri Khan |
Subject: |
Re: puzzle with string permutations [photo] |
Date: |
Tue, 7 Jun 2022 23:09:36 +0700 |
On Tue, 7 Jun 2022 at 21:18, Emanuel Berg <incal@dataswamp.org> wrote:
> It doesn't work exactly like that with strings, since for
> example the scrambled word "ogod" is actually, here, treated
> as
>
> o_1 g o_2 d
>
> Yet the words
>
> g o_1 o_2 d
> g o_2 o_1 d
>
> are duplicates.
This extension of the concept of sets is called a multiset or a bag.
For each element, we also have a multiplicity. Let’s write it as {o:2,
g:1, d:1}.
Let’s solve the problem: Given a multiset of letters {X_1:n_1, …,
X_k:n_k}, how many distinct strings using up all of them are there?
First, we treat repeating letters as if they were distinct, e.g. by
numbering them as you did above: {o_1, o_2, g, d}. These are 4 letters
and there are 4! = 24 permutations.
However, every two permutations that only differ by the order of o_1
and o_2 are equivalent in our original unnumbered multiset. So we have
to divide by two: 4! / 2 = 24 / 2 = 12. dgoo, dogo, doog, gdoo, godo,
good, odgo, odog, ogdo, ogod, oodg, oogd.
What do we do if there are three or more instances of each letter?
Let’s consider a degenerate multiset {w:3}. If we number the
instances, it’s {w_1, w_2, w_3} and there are 3! = 6 permutations, but
clearly the only distinct string is www. So it looks like we need to
divide by 3! = 6: 3! / 3! = 6 / 6 = 1.
In general, with a multiset {X_1:n_1, …, X_k:n_k}, if we number each
letter, we get (n_1 + … + n_k)! permutations, and then we have to
adjust for duplicates for each individual letter by dividing by (n_1)!
… (n_k)!.
n_perm = (n_1 + … + n_k)! / (n_1)! … (n_k)!
For the above example of {o:2, g:1, d:1}:
n_perm = (2 + 1 + 1)! / 2! 1! 1! = 4! / 2 1 1 = 24 / 2 = 12.
(This problem was part of my exam in maths when I was applying at
Novosibirsk State University, Mechanics & Maths Department, in 1997.)
(You might also notice the formula is similar to that of a binomial
coefficient: C_{n,k} = n! / k! (n-k)!. That’s no coincidence.)
- puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo], Marcin Borkowski, 2022/06/07
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo],
Yuri Khan <=
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07
- missing Lisp world (was: Re: puzzle with string permutations [photo]), Emanuel Berg, 2022/06/07
- Re: puzzle with string permutations [photo], Emanuel Berg, 2022/06/07