Avoiding Loops!

Question

Given a collection of coloured laces, what would be the probability, \$P\$, that Alice won't create any loops if, until impossible, they tie two uniformly chosen, free lace ends of differing colours together?

For the avoidance of doubt:

• Each lace will be of only one colour and will have precisely two ends.
• Alice does not choose lace ends, rather they are selected by a random process such that each pair of free lace ends with differing colours is equally likely.
• Once Alice has tied two lace ends together they become unavailable (i.e. they are no longer "free lace ends").
• If, at any point, there are no pairs of free lace ends of differing colours and no loops, Alice is done and has successfully avoided creating any loops.

I/O:

Input: Any reasonable representation of the collection of laces.

Some suggestions (the examples in this section are for a collection of six laces, one red, two green, and three blue):

• A list of colour counts (as used in the Examples and Tests sections)
  ([1, 2, 3])
• A list of lace colours as numbers or strings
  (["red", "green", "green", "blue", "blue", "blue"])
• A list of laces as pairs of equal numbers or strings
  ([("red", "red"), ("green", "green"), ("green", "green"), ("blue", "blue"), ("blue", "blue"), ("blue", "blue")])
• A list of lace ends as lace colour, lace identifier pairs
  ([("red", 1), ("red", 1), ("green", 2), ("green", 2), ("green", 3), ("green", 3), ("blue", 4), ("blue", 4), ("blue", 5), ("blue", 5), ("blue", 6), ("blue", 6)])

The input may be assumed to be pre-sorted in any order.

Output: The probability of making no loops.

• This may be a numerator, denominator pair (in either, specified order), a fraction object, a floating point number, etc.
• Type or machine inaccuracies are acceptable as long as the method is fundamentally sound but if these do adversely affect the test case results then do try to provide an alternative without inaccuracies.
• This is probability-theory, so you may not approximate the result by sampling (but do feel free to enumerate all possibilities).

Scoring

This is code-golf, so try to minimise the bytes of code in your language of choice.

Examples

Using colour counts, sorted ascending...

[2] (e.g. two blue laces)
No lace ends can be tied together since all four are of the same colour, thus no loop may be made, so \$P = 1\$.

[1, 1] (e.g. one black lace and one white lace)
All four initial choices of pairs of lace ends of differing colours produce a single string of the two laces, with ends of different colours. At this point, the only option is to tie the two remaining lace ends together forming a loop and thus \$P=0\$.

[1, 2] (e.g. one red lace and two green laces)
The only available first move is to tie one end of the unique lace to one end of either of the other two laces, after which we'll be left with a string of two differently coloured laces along with a lone lace of the more common colour. At this point, one of the two ends we pick must be the remaining end of the unique lace, which is on the string, and the other must be one of the three remaining ends of the other colour. One of these lace ends is on the other end of the string and would form a loop, while the other two lace ends will result in a single string formed of all three laces with the unique lace in the middle whereupon no loop may be formed and thus \$P=\frac{2}{3}\$.

[1,4] (e.g. one pink lace and four yellow laces)
This follows much the same logic as [1,2]. We must first form a string from the unique lace and another. Then we only form a loop if we pair the remaining uniquely coloured lace end with the other end of the string it is on otherwise we pair with one of the other six lace ends and create a string of three laces with the unique lace in the middle at which point all available lace ends will be of one colour, so \$P=\frac{6}{7}\$.

[2,3] (e.g two orange laces and three purple laces)

Rather than even more words, the below starts with OO OO PP PP PP and enumerates the next possible states, with L for a loop and strings represented as their two free lace ends (enumeration stops whenever a loop is formed, and equivalent states at any step have been collapsed):

      OO OO PP PP PP

   1) OP OO PP PP  (24/24)...

  1A) OO PP PP     (6/15)...
  1B) OP OP PP     (8/15)...
  1C) L OO PP PP   (1/15) loop

 1A1) OP PP        (8/8)...

 1B1) OP PP        (6/8)...
 1B2) L OP PP      (2/8) loop

1A1A) PP           (2/3) no loop
1A1B) L PP         (1/3) loop

1B1A) PP           (2/3) no loop
1B1B) L PP         (1/3) loop

P = P(1A1A) + P(1B1A)

...so \$P = \frac{2}{3}\frac{8}{8}\frac{6}{15}\frac{24}{24} + \frac{2}{3}\frac{6}{8}\frac{8}{15}\frac{24}{24} = \frac{4}{15} + \frac{4}{15} = \frac{8}{15}\$

Test Cases

Using colour counts, sorted ascending...

             [] => 1                   = 1/1
            [1] => 1                   = 1/1
            [2] => 1                   = 1/1
         [1, 1] => 0                   = 0/1
         [1, 2] => 0.6666666666666666  = 2/3
         [1, 3] => 0.8                 = 4/5
         [1, 4] => 0.8571428571428571  = 6/7
         [1, 5] => 0.8888888888888888  = 8/9
         [2, 2] => 0                   = 0/1
         [2, 3] => 0.5333333333333333  = 8/15
         [3, 3] => 0                   = 0/1
      [1, 1, 2] => 0.2736700336700337  = 2032/7425
      [1, 2, 2] => 0.12555631502999923 = 8266/65835
      [2, 2, 2] => 0.13119594210503302 = 75008/571725
      [2, 2, 3] => 0.1917063718196613  = 3352734487913/17488904808375
   [1, 1, 2, 2] => 0.10567693844206749 = 190686196363904/1804425820572375
   [1, 1, 2, 3] => 0.2161161470046424  = 4948035616451519666768/22895261113207012454925

Answer 1

Charcoal, 97 93 bytes

≔⟦⊞ＯＡ¹⟧θＦθ«≔⊟ιη≔⟦⟧ζＦＬιＦΦκ⁻§ιλ§ικ⊞ζ⟦λκ⟧¿ζＦΦζ↨÷κ²±¹⊞θ⊞ＯＥΦι⁻÷μ²÷⌈κ²⎇⁼μ⌊κ§ι⁻｜⌈κ¹＆⌈κ¹λ∕ηＬζ⊞υη»Ｉ↨υ¹

Try it online! Link is to verbose version of code. Takes input as a flat list of lace end numbers and uses floating-point arithmetic to calculate the probability. Explanation: Brute force enumeration of lace tie patterns.

≔⟦⊞ＯＡ¹⟧θＦθ«

Start a breadth-first search with the input pattern with a probability of 1.

≔⊟ιη

Get the probability of this pattern.

≔⟦⟧ζＦＬιＦΦκ⁻§ιλ§ικ⊞ζ⟦λκ⟧

Get the list of tieable lace end pair indices.

¿ζ

If the list is not empty, then:

ＦΦζ↨÷κ²±¹

Loop over the pairs of ends that don't form a loop.

⊞θ⊞ＯＥΦι⁻÷μ²÷⌈κ²⎇⁼μ⌊κ§ι⁻｜⌈κ¹＆⌈κ¹λ∕ηＬζ

Get the updated pattern after the current pair of ends are tied, include the new probability of this pattern, and save this to the list of patterns to search.

⊞υη

Otherwise, push the probability of this pattern to the running total.

»Ｉ↨υ¹

Output the final total.

Answer 2

Python, ¹⁴⁶ 142 bytes

f=lambda x,*_:sum(s:=[(n!=m)*f(y:=[(c,o-n or m-n)for c,o in x],*map(y.remove,[(a,m-n),(b,m-n)]))for a,n in x for b,m in x if a-b]or[1])/len(s)

Attempt This Online!

Takes input as a list of lace ends as lace color, lace identifier pairs with both represented as integers

f = lambda x, *_:
  sum(                              # sum(
    s := [                          #   s = [
      (n != m) *                    #     0 if same lace else
      f(                            #     recursive call with
        y := [                      #       y = [
          (c, o - n or m - n)       #         subtract n from identifer but set to m - n for n
          for c, o in x             #         for each lace end
        ],                          #       ]
        *map(                       #
          y.remove,                 #       remove from y
          [(a, m - n), (b, m - n)]  #       the chosen lace ends
        )                           #
      )                             #
      for a, n in x                 #     for each lace end a = color, n = identifier
      for b, m in x                 #     for each lace end b = color, m = identifier
      if a - b                      #     if different colors
    ]                               #   ]
    or                              #
    [1]                             #   s = [1] if all lace ends have same color
  ) / len(s)                        # ) / len(s)

---

Python, ^{159 157} 153 bytes

-2 bytes thanks to @Jonathan Allan

f=lambda x,*_:sum(s:=[a is not b and f(y:=x+[(a[q>1],b[~q%2])],*map(y.remove,[a,b]))for a in x for b in x for q in range(4)if a[q<2]-b[q%2]]or[1])/len(s)

Attempt This Online!

Takes inputs as a list of laces as pairs of equal numbers

Answer 3

JavaScript (ES6), 138 bytes

-11 thanks to Mukundan314

Expects an array of laces, where each lace is a pair of integers representing its ends (e.g. [0,0]).

f=(a,n=t=0)=>a.map(p=>a.map(q=>[0,1,2,3].map(x=>t+=p[x>>1]-q[x&1]&&++n&&p!=q&&f([...a.filter(r=>r!=p&r!=q),[p[x/2^1],q[~x&1]]]))))|n?t/n:1

Try it online!

Commented

f = (                     // f is a recursive function taking:
  a,                      //   a[] = input array
  n =                     //   n = counter
  t = 0                   //   t = sum
) =>                      //
a.map(p =>                // for each lace p in a[]:
  a.map(q =>              //   for each lace q in a[]:
    [0, 1, 2, 3]          //     there are 4 possible connections
    .map(x =>             //     for each connection x:
      t +=                //       update t:
        p[x >> 1] -       //         if the end of p does not
        q[x & 1] &&       //         match the end of q,
        ++n &&            //         then increment n
        p != q &&         //         if p and q are different laces,
        f([               //         then do a recursive call:
          ...a.filter(    //           pass a copy of a[]
            r =>          //           where:
            r != p &      //             the lace p and the lace q
            r != q        //             are removed
          ),              //           end of filter()
          [ p[x / 2 ^ 1], //           and a new lace made of the
            q[~x & 1] ]   //           opposite ends is added
        ])                //         end of recursive call
    )                     //     end of map()
  )                       //   end of map()
) |                       // end of map()
n ?                       // if n is not zero:
  t / n                   //   return the probability t / n
:                         // else:
  1                       //   return 1

Answer 4

Python3, 497 bytes

lambda x:sum(f(x))
E=enumerate
S=sorted
u=lambda x:str(S(map(S,x)))
def f(a,p=1):
 if len(a)==1:yield p*(a[0][0]==a[0][1]);return
 d={}
 for i,j in E(a):
  if j[0]!=j[-1]:n=u(a[:i]+a[i+1:]);d[(n,0)]=d.get((n,0),0)+1
  for I,J in E(a):
   if i<I:
    F=[y for x,y in E(a)if x not in[i,I]]
    for j in[j,j[::-1]]:
     for J in[J,J[::-1]]:
      if j[-1]!=J[0]:n=u(F+[j[:-1]+J[1:]]);d[(n,1)]=d.get((n,1),0)+1
 if{}==d:yield p
 for x,y in d:
  if y:yield from f(eval(x),p*(d[(x,y)]/sum(d.values())))

Try it online!