back to article Combinations? Permutations? Those words don't mean what you think they mean

At the heart of machine learning are patterns, and patterns are all about counting, so it's important to make sure we are counting the correct items in the correct way. Combinatorics is the branch of mathematics concerned with counting things; more specifically, all the wonderful ways you can count, arrange and manipulate finite …

  1. Ralph the Wonder Llama
    Coat

    "Pedantically, neither of these phrases are correct"

    Pedantically, neither of those sentences are phrases, they are questions.

    One of those days. See icon.

    1. The Indomitable Gall

      Re: "Pedantically, neither of these phrases are correct"

      Regardless, pedantically both are correct, because of something called polysemy....

      1. Commswonk

        Re: "Pedantically, neither of these phrases are correct"

        Pedantically neither of these phrases is correct.

  2. Pangasinan Philippines

    How I always remembered it

    If you're interested, you win the lottery with a combination (not a permutation) and technically you unlock a safe with a permutation (not a combination). ®

    In my day it was the football permutations by Littlewoods.

    1. Simon Harris

      Re: How I always remembered it

      Combination locks...

      Mechanical combination locks such as these...

      http://www.codelocks.co.uk/cl200/cl200-surface-deadbolt.html

      actually are true combination locks, rather than permutation locks. You can press the buttons for the combination in any order you want (or all together if you insist) and they will unlock.

      (not counting the 'C' button which just clears the mechanism rather than being part of the actual combination).

      I was quite disappointed to discover that they were not nearly as secure as I had assumed.

      The locks have 0..9XYZ characters, so the security of guessing a 5 character code drops from a 1 in 371293 chance to 1 in 1287.

      1. This post has been deleted by its author

      2. This post has been deleted by its author

        1. Simon Harris

          Re: How I always remembered it

          You are right, the 8191 figure is derived from summing the combinations from 1 of 13, 2 of 13 through 13 of 13.

          1. Anonymous Coward
            Anonymous Coward

            Re: How I always remembered it

            > You are right, the 8191 figure is derived from summing the combinations from 1 of 13, 2 of 13 through 13 of 13

            Although that's correct, it can be done more simply: each button is either "in" or "out" (2 choices), and the correct combination is a unique permutation of ins and outs, so it's just 2^13 - the same as the number of different values of a thirteen-bit binary number.

            Minus one to exclude the all-out (all-zeros) combination which would mean your door is unlocked by default.

            1. Simon Harris

              Re: How I always remembered it

              It's always gratifying when you can think of a problem in two different ways and the maths works out!

            2. swm

              Re: How I always remembered it

              I was in a high school math class and one of the students asked how many chords on the piano there were (not distinguishing notes an octave apart). The instructor started by calculating 12 single notes plus 12.11/1.2 double notes plus ... . I looked up from the science fiction novel I was reading (I was bored) and said 4096 or 4095 if you don't count silence. The instructor wrote 4095 on the board and continued his computation. When he finally got the (obvious to me) answer he just looked at me and changed the subject. Even in 1960 I was playing with computers and knew powers of two cold but some people are easily impressed.

              1. DropBear
                Happy

                Re: How I always remembered it

                Have them all permanently etched in up to 2^16 ever since the Spectrum days...

      3. AndGregor
        Thumb Up

        Re: How I always remembered it

        Six times out of ten the combination is set to 4 digits in a convenient block so that a sideways thumb press will deal with the four numbers, then just select the letter.

      4. John Smith 19 Gold badge
        Unhappy

        actually are true combination locks, can press the buttons..in any order

        So are the "key safes" used for emergency access to peoples properties with dementia.

        They many know the numbers, they just can't recall the order.

        1. This post has been deleted by its author

      5. The Indomitable Gall

        Re: Mechanical combination locks

        It gets worse.

        A lot of people don't change the codes very often, and the action behind keys that are used most tends to soften fairly quickly. There have been times where I've forgotten the combination to a room/building and reminded myself by just prodding all the buttons until I find the soggiest ones, which then let me in. Scarily weak security.

        1. Stoneshop
          Holmes

          Re: Mechanical combination locks

          A lot of people don't change the codes very often, and the action behind keys that are used most tends to soften fairly quickly.

          Similar problem with electronic locks using a keypad: you can often see the keys in use as having a grimy area around them and/or being more worn, so it's now merely a matter of finding the right permutation of those keys.

      6. Evil Auditor Silver badge

        Re: How I always remembered it

        I was quite disappointed to discover that they were not nearly as secure as I had assumed.

        They look pretty insecure to me in the first place. Before trying any combination you'd rather crack open the whole lock. If you can't figure the combination from the dirt on the right keys, that is.

        Anyway, those locks are not really made to secure anything. They are rather there against accidentally opening the wrong door.

    2. BongoJoe

      Re: How I always remembered it

      Indeed the 'perms' should have been called 'combs'.

      One of the first thing I learned in sixth form statistics in the seventies.

  3. Anonymous Coward
    Anonymous Coward

    Hmm, Finite does not mean limited

    It means its definable, this does not, strictly (pedantically) speaking, mean limited.

    I had better read the rest of the article now!

    1. Brangdon

      Re: Hmm, Finite does not mean limited

      It's more common to encounter the flip side of that: people saying "infinite" when they mean "unbounded". For example, a Turing Machine doesn't have infinite tape, it has unbounded tape. It will never use more than a finite portion of it, but there is no upper bound on how large that portion can be.

  4. Anonymous Coward
    Anonymous Coward

    Thank-you...

    for this article and the excellent comments so far.

  5. Jim 59

    Oh yes they do

    Phrase/sentence howler - come on Ed.

    "You might have heard the words "combination" or "permutation" used in conversation..."

    Permutaions and combinations are not news to Reg readers. This isn't the Grauniad.

    "...mathematics has a convenient formula for the calculations shown above and you can search the internet for it... "

    Or just remember it from school. Not a bad article, despite my sniping. Just told to the wrong people.

    1. Anonymous Coward
      Anonymous Coward

      Re: Oh yes they do

      Oh I don't know - it's been so long I'd forgotten which way round the names were (although not the significance of why they're different). It's nice to get a refresher.

  6. Natalie Gritpants

    I often go back and forth on websites, e.g.

    Home page

    Account Cancelation

    Are you sure? with OK/Cancel

    Back to home page as I clicked Cancel

    ...

  7. ForthIsNotDead
    Coat

    I admit it...

    I clicked on the article because of the pretty girls in the picture.

    1. Aladdin Sane
      Trollface

      Re: I admit it...

      "clicked"

  8. DHBI

    HSE

    Why aren't they wearing seatbelts in the picture?

    1. Anonymous IV
      Happy

      Re: HSE

      > Why aren't they wearing seatbelts in the picture?

      a) because the car is not in motion

      b) because they are Americans

      c) they are young, so they think they will live forever

      1. Hero Protagonist

        Re: HSE

        ...or some, er, combination of the three

  9. Ugotta B. Kiddingme

    Re: A Parting Note for the Pedants

    "If you're interested, you win the lottery with a combination (not a permutation)"

    While this is technically true for most lottery games, it is not true for all. Some "smaller" lottery games (Pick 3 numbers instead of 6, etc) have much smaller payouts but pay a bonus or, in this example, provide the highest payout for the smallest buy-in if you get the winning numbers in the correct order (therefore, permutation)

  10. Frumious Bandersnatch

    you missed an opportunity in the article

    to talk about how programmers actually code up the selection of a random combination or permutation. You need something like a Fisher-Yates shuffle (using lists) or Floyd's algorithm (using sets) to ensure that the results aren't biased in some way.

    It's all to easy to come up with a naive algorithm for, eg, dealing a hand from a deck of cards that seems to work but favours picking certain hands over others.

    1. DropBear
      Facepalm

      Re: you missed an opportunity in the article

      You don't even need combinatorics for that. Point a wallpaper changer - any wallpaper changer - set to random at a library of a thousand photos, watch them cycle between the same ten every. single. time.

  11. Lee D Silver badge

    A pseudo-maths article, that's unusual.

    Though the bit I like about perms and combs is that it's a perfect demonstration of factorials. Factorials get out of hand REALLY quickly - 21! won't fit in a 64-bit number, for instance, and just 69! is enough to exceed most calculator's display capacity (even with exponents up to 10^99 and complete loss of accuracy). And something like 449! is an incredibly difficult-to-handle number (> 10^999).

    However, nPr and nCr are basically multiples of large factorials (e.g. 49 choose 6 for the lottery: 49! / (6! x 43!) ). But, because of what a factorial is - every number up to itself multiple together - they cancel out really fabulously so you never have to have 1024-bit numbers to work them out.

    It's little things like that that make maths beautiful - eliminating the need to do ridiculously large calculations by just using the right notation and a little algebra.

    1. Gezza

      re: pseudo-maths

      It's a Shriek (the exclamation mark in that equation). At least, that is what our maths master called it at school although we're talking '70's here so I may be the only one now.

      1. pdh

        Re: re: pseudo-maths

        > It's a Shriek (the exclamation mark in that equation)

        When I was in school (decades ago) I also heard it called "admiration" -- that is, some people pronounced 3! as "three admiration." I was told that was a British thing (I went to school in the U.S.)... is there any truth to that?

        1. Anonymous Coward
          Anonymous Coward

          Re: re: pseudo-maths

          @pdh

          I'm British, and I've never heard of it being called "admiration" before. Usually it's named as "exclamation mark", though I have heard it referred to as "bang" (which seemed odd at the time). In a mathematics context people normally just say "factorial" though, seeing as that's what it's actually denoting.

          1. Richard Parkin

            Re: re: bang!

            Bang is a typographical term for !

      2. David Roberts

        Re: re: pseudo-maths

        Shriek AKA bang, IIRC.

        Can't remember the context of each useage but both were computing. Just shorter than saying "exclamation mark".

        1. Loyal Commenter Silver badge

          Re: re: pseudo-maths

          Also 'Pling', which is the one I heard when at school many moons ago.

          1. Anonymous Coward
            Happy

            Re: re: pseudo-maths

            Now known as the OMG.

        2. Phil O'Sophical Silver badge

          Re: re: pseudo-maths

          George 3 (the OS, not the mad monarch) would allow you to create temporary work files called !, and these were created in a stack. Create two work files and you could reference one as ! and the other as !-1. Add another and it became ! and the existing ones !-1 and !-2.

          For convenience we always called them shriek files, referred to as "shriek" "shriek minus one" etc.

    2. Steve the Cynic

      "Factorials get out of hand REALLY quickly - 21! won't fit in a 64-bit number, for instance, and just 69! is enough to exceed most calculator's display capacity (even with exponents up to 10^99 and complete loss of accuracy). And something like 449! is an incredibly difficult-to-handle number (> 10^999)"

      Factorial can, for large enough n, be approximated by sqrt(n)*pow(n,n)/exp(n).

      pow(n,n) gets very large very quickly. 1, 4, 27, 256, 3125, 46656, 823543, ... In particular, it gets very large much faster than exp(n) (e to the power n).

      And the IEEE-754 "long double" (80-byte floating point) can handle exponents of 10 beyond 4900. Of course, modern compilers tend not to support it since SSE floating point is much faster than x87 NPU floating point, and SSE does not understand long double. If you can track down a copy of VC++6, though, you're in business.

      1. Steve the Cynic

        "IEEE-754 "long double" (80-byte floating point)"

        Of course I needed to proofread that before I posted it. 10 bytes or 80 bits, not 80 bytes!

    3. Lee D Silver badge

      Have a UK maths degree.

      Have never referred to it as a shriek. Or a bang. Both are quite American, I think. Yes, even in the Unix shell-script !/bin/sh sense, I don't call them shrieks or bangs.

      Never heard of the other words used in this thread either.

      It's an exclamation mark (if in speech / symbol) or it's a mathematical mark: "x factorial". Or it's possibly "NOT" if used as a logical operator.

      The one in UNIX paths, I don't call anything in particular because how often do you have to explain to someone to type in a ! into a shell script who doesn't already know exactly how to do so?

      I guarantee that if you try to read out a password with an "!" in it to a random person, they won't understand shriek or bang or pling. But they know what an exclamation mark is. Hell, even "hash" for # confuses people ("Yes, it's the little noughts-and-crosses board" "What's noughts and crosses? You mean Tic-Tac-Toe?" etc... it might be called 'hash' or 'pound' (US) or 'octothorpe' or, to music people 'sharp' but if you choose any one of those when talking to a random person you have about a 50% chance of success - if anything "hashtag" actually works better but I refuse to call the symbol that, and people often don't know what "hash" on its own means).

  12. anthonyhegedus Silver badge

    I used to work for someone who thought I was pedantic. One day she told me "stop being so pendantic". So I said "It's PEDantic not PENDantic". The irony just went right over her head.

    1. Loyal Commenter Silver badge

      ...Maybe she was doing it deliberately, and the irony went over your head.

      1. anthonyhegedus Silver badge

        "...Maybe she was doing it deliberately, and the irony went over your head."

        No... seriously... no!

  13. GlenP Silver badge

    If anyone wants to know more about this I can lend you "An Introduction to Computational Combinatorics"! Still got it over 30 years after I left Uni, and still can't read it without falling asleep.

  14. anonymous boring coward Silver badge

    Nice clickbait!

    Who is Dick in that photo?

    1. Anonymous Coward
      Anonymous Coward

      Re: Who is Dick in that photo?

      You get to find out like Begbie after pub

  15. Anonymous Coward
    Linux

    Forget the numbers....

    Why do I feel like going out to buy an Asus eeepc after seeing that picture?

  16. Phil Endecott

    > Assuming your data set is large, and there are many visits to the

    > website, you're likely to apply machine learning (ML) in your

    > investigations.

    Nope.

    I'm just going to use "a program".

    Or is "machine learning" just how people spell "a computer program" these days?

    1. Anonymous Coward
      Anonymous Coward

      "Or is "machine learning" just how people spell "a computer program" these days?"

      Only 1 upvote allowed??

  17. Adam 1

    > This could be all the different ways in which three out of your five friends could enter the car via the passenger seat (you are already seated)

    Wait, are you trying to trick me into proving N != NP ?

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Other stories you might like