Copyright © Philip M. Parker, INSEAD. Terms of Use.
Definition: Permutation |
PermutationNoun1. An event in which one thing is substituted for another; "the replacement of lost blood by a transfusion of donor blood". 2. The act of changing the arrangement of a given number of elements. 3. Complete change in character or condition: "the permutations...taking place in the physical world"- Henry Miller. 4. Act of changing the lineal order of objects in a group. Source: WordNet 1.7.1 Copyright © 2001 by Princeton University. All rights reserved. |
Date "permutation" was first used in popular English literature: sometime before 1385. (references) |
Etymology: Permutation \Per`mu*ta"tion\, noun. [Latin expression permutatio: compare to the French expression permutation. See Permute.]. (references) |
| Domain | Definition |
Computing | Permutation |
Math | A rearrangement of elements, where none are lost, added, or changed. A good algorithm to randomly permute N elements is to exchange each element ei with a random element from i to N. (references) |
Statistics | The process of generating alternative arrangements of given data which would be consistent with the experimental design. Source: European Union. (references) |
Source: compiled by the editor from various references; see credits. | |
(From Wikipedia, the free Encyclopedia)
In mathematics, a permutation is a sequence of elements in which no element appears more than once. In a sequence, unlike in a set, the order in which the elements are written down matters. Suppose you have a total of n distinct objects at your disposal and you want to create permutations of r elements selected from those n, where r≤n.In how many ways can that be done?
Summarizing, we find that a total of
- We can select the first member of the list in n ways because there are n distinct elements.
- The second member of the list can be filled in (n-1) ways since we have used up one of the n elements already.
- The third member can be filled in (n-2) ways since 2 have been used already.
- This pattern continues until there are r names on the list. This means that the last member can be filled in (n-r+1) ways.
different permutations of r objects, taken from a pool of n objects, exist. If we denote this number by P(n, r) and use the factorial notation, we can write
- n * (n-1) * (n-2) * ... * (n-r+1)
Other, older notations include nPr, Pn,r, or nPr. Often, when using TeX or otherwise, the P(n,r) method is the simplest to typeset.
- .
In modern mathematical terminology, such as that used in professional combinatorics, the word permutation is now rarely used except in the case r=n.
See also Combinations, Josephus permutation.
In abstract algebra and other fields, the term permutation is usually reserved for a bijective map from a set to itself. Some of the older textbooks do look at permutations an alternative way (essentially as assignment operations); the difference could be used to illustrate one way in which functional programming and imperative programming differ. The convention, though, is now that permutations are just functions and the operation on them is function composition.
There are two main notations for such permutations. In relation notational, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row:
In cycle notation, one can write the cycles induced by the permutation; that is, one takes any element (say 1); then the element the first one is being sent to (here 2); then the element this one is sent to (here 5), and so on, until one comes back to the first. This is a cycle. The next cycle begins with any other element not considered till now, until every element appears in a cycle. So the previous permutation has cycle form (1 2 5)(3 4). Of course, the same permutation could be written as (4 3)(2 5 1), or any other variant, but the "canonical" form for a permutation places the lowest-numbered position in each cycle first in that cycle and then orders the cycles by increasing first element.
This notation often omits fixed points, that is, elements mapped to themselves; thus (1 3)(2)(4 5) can become simply (1 3)(4 5).
A permutation consisting of one cycle is itself called a cycle. The number of entries of a cycle is called the length. For example, the length of (1 2 5) is three.
The identity permutation is the permutation which maps each element to itself.
Given a permutation P, the identity permutation I, P's inverse permutation P-1 is the permutation that undoes P, ie., performing P then P-1 is the same as performing the identity permutation.
A transposition is a permutation which exchanges two elements and keeps all others fixed. For example (1 3) is a transposition. A transposition is a cycle of length two.
One can define product of two permutations, see Symmetric group and Permutation group. An even permutation is a permutation which can be expressed as a product of even number of transpositions, and the identity permutation is a even permutation as it equals (1 2)(1 2). An odd permutation is an permutation which can be expressed as a product of odd number of transpositions.
A permutation matrix is a matrix representation of permutation.
Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Permutation."
Synonyms: PermutationSynonyms: replacement (n), substitution (n), switch (n), transposition (n). (additional references) |
| Context | Synonyms within Context (source: adapted from Roget's Thesaurus). |
Change | Noun: change, alteration, mutation, permutation, variation, modification, modulation, inflexion, mood, qualification, innovation, metastasis, deviation, turn, evolution, revolution; diversion; break. |
Difference | Noun: difference; variance, variation, variety; diversity, dissimilarity; disagreement; disparity; (inequality); distinction, contradistinction; alteration. modification, permutation, moods and tenses. |
Interchange | Noun: interchange, exchange; commutation, permutation, intermutation; reciprocation, transposition, rearrangement; shuffling; alternation, reciprocity; castling; hocus-pocus. |
Number | Permutation, combination, variation; election. |
| Source: adapted from Roget's Thesaurus. | |
Crosswords: Permutation |
| Specialty definitions using "permutation": bijection, bogosort ♦ perfect shuffle ♦ shift algorithm ♦ tensor product. (references) |
| Non-English Usage: "Permutation" is also a word in the following languages with English translations in parentheses. French (interchange, permutation), German (permutation), Swedish (permutation). |
| Domain | Title | ||
Books |
| ||
Music |
| ||
Source: compiled by the editor from various references; see credits. | |||
| "Permutation" is generally used as a noun (singular) -- approximately 100.00% of the time. "Permutation" is used about 29 times out of a sample of 100 million words spoken or written in English. Its rank is based on over 700,000 words used in the English language. Some parts-of-speech are not covered due to the samples used by the British National Corpus. (note: percents less than one-hundredth of one percent have been omitted) |
| Parts of Speech | Percent | Usage per 100 Million Words | Rank in English |
| Noun (singular) | 100% | 29 | 64,444 |
Source: compiled by the editor from several corpora; see credits.
Expression using "permutation": permutation lock. Additional references. | |
| Source: compiled by the editor from various references; see credits. |
| The following statistics estimate the number of searches per day across the major English-language search engines as identified by various trade publications. Hyperlinks lead to commercial use of the expression at Amazon.com. |
| Language | Translations for "permutation"; alternative meanings/domain in parentheses. | |
Albanian | permutacion, ndryshim (alteration, amendment, change, difference, disparity, dissimilarity, dissimilation, dissimilitude, distinction, inflection, inflexion, innovation, manipulation, metamorphosis, modification, mutation, recast, reversal, reverse, shift, shifting, switch, transit, transition, turn, variation), ndërrim (change, commutation, exchange, proselytism, shift, substitution, transfiguration). (various references) | |
Arabic | تغير أساسي, تعديل (adjustment, alteration, amendment, arrangement, conformation, correction, focussing, mend, mitigation, modification, modulation, overhaul, revise), تبديل (alteration, change, commutation, replacement, variation), التبدلة. (various references) | |
Bulgarian | промяна (alteration, change, chop, countermarch, innovation, mutation, reversal, sea change, shift, transition, transmutation, turn, turnover, variance, variation), пермутация, изменение (alteration, amendment, change, change over, innovation, mutation, turn, variation). (various references) | |
Chinese | 变更. (various references) | |
Czech | permutace, obmìna (diversification). (various references) | |
Danish | permutation (re-randomisation), rerandomisering (re-randomisation). (various references) | |
Dutch | permutatie (re-randomisation). (various references) | |
Farsi | قلب وتحریف , استحاله . (various references) | |
Finnish | permutaatio (re-randomisation). (various references) | |
French | permutation. (various references) | |
German | Permutation (re-randomisation), Vertauschung (changing, exchange, mix up, mixing up, reversal, transposition), Umsetzung (breakdown, conversion, redeployment). (various references) | |
Greek | μετάθεσις, μετάθεση (metathesis, relegation, removal, transfer, transposition), μεταλλαγή (alteration, mutation, transformation, transmutation), ανταλλαγή (commutation, exchange, interchange, reciprocation). (various references) | |
Hebrew | תמור" (barter, change, exchange, recompense, substitution, value), חלוף (ephemeral, exchange, replacement, reverse, variation). (various references) | |
Hungarian | permutáció. (various references) | |
Italian | permutazione (re-randomisation). (various references) | |
Japanese Kanji | 列 . (various references) | |
Japanese Katakana | じゅ"れつ. (various references) | |
Korean | 순열. (various references) | |
Manx | co-choonrey (barter). (various references) | |
Pig Latin | ermutationpay.(various references) | |
Portuguese | permutação (exchange, transposition). (various references) | |
Romanian | permutare, schimbare totalã, rearanjare. (various references) | |
Russian | перестановка (interchanging, rearrangement, reshuffle, reversal, reversion, shift, transposal, transposition). (various references) | |
Serbo-Croatian | permutacija, razmena (commutation, exchange, interchange, swap, trade). (various references) | |
Spanish | permutación (re-randomisation). (various references) | |
Swedish | permutation. (various references) | |
Turkish | permutasyon, yer değiştirme (removal, shift, shuffle, substitution, supersession), değişim (alteration, change, changing, meta-, metamorphosis, mutation, switch, turn, variation), değiş tokuş (barter, exchange, swap, swop, truck). (various references) | |
Ukrainian | метатеза (metathesis), пермутування, перестановка (interchange, inversion, rearrangement, reshuffle, reversion, transposal, transposition). (various references) | |
Vietnamese | pháp hoán vị. (various references) | |
Welsh | amnewidiad. (various references) | |
| Source: compiled by the editor from various translation references. | ||
Derivations | |
Words beginning with "permutation": permutational, permutations. (additional references) | |
| |
"Permutation" is suggested in spellcheckers for the following: permitation, permition, permutating, permutational, perumutation, premutation. (additional references) | |
| Source: compiled by the editor, based on several corpora (additional references). | |
| # of Phoneme Matches | Pronunciation | Word(s) rhyming with "permutation" (pronounced per'myuwtā"shun) |
| 8 | -m y uw t ā" sh u n | mutation. |
| 7 | -y uw t ā" sh u n | disputation, refutation. |
| 5 | -t ā" sh u n | facilitation, fermentation, accreditation, adaptation, affectation, agitation, amputation, annotation, argumentation, augmentation, cetacean, citation, cogitation, cohabitation, computation, confrontation, connotation, consultation, crustacean, decapitation, deforestation, deportation, devastation, dictation, dilatation, disorientation, dissertation, documentation, equitation, excitation, exhortation, expectation, experimentation, exploitation, flirtation, flotation, fragmentation, gestation, gravitation, habitation, hesitation, imitation, implantation, implementation, importation, imputation, incantation, incapacitation, incrustation, indentation, infestation, inhabitation, instrumentation, interpretation, invitation, irritation, lactation, levitation, limitation, manifestation, meditation, misinterpretation, misrepresentation, molestation, notation, orientation, ornamentation, ostentation, palpitation, pigmentation, plantation, precipitation, premeditation, presentation, protestation, quotation, recantation, recitation, reforestation, regimentation, rehabilitation, reinterpretation, representation, reputation, resuscitation, rotation, sanitation, sedimentation, segmentation, solicitation, station, superstation, temptation, transplantation, transportation, vegetation, visitation. |
| 4 | -ā" sh u n | falsification, fascination, federation, fertilization, fibrillation, figuration, filtration, abrogation, acceleration, acclimation, accommodation, abbreviation, abdication, aberration, abomination, accumulation, accusation, acidification, activation, adjudication, administration, admiration, adoration, adulation, advocation, affiliation, affirmation, agglomeration, aggravation, alienation, allegation, alleviation, allocation, alphabetization, alteration, altercation, amalgamation, amelioration, amortization, amplification, animation, annexation, annihilation, anticipation, antidiscrimination, appellation, application, appreciation, approbation, appropriation, approximation, arbitration, articulation, aspiration, assassination, assimilation, association, authentication, authorization, automation, aviation, avocation, balkanization, bifurcation, calculation, calibration, cancellation, cannibalization, capitalization, capitulation, carnation, castration, categorization, causation, celebration, centralization, certification, cessation, characterization, civilization, clarification, classification, coagulation, codification, cogeneration, collaboration, collectivization, colonization, coloration, colorization, combination, commemoration, commendation, commercialization, communication, communization, compensation, compilation, complication, computerization, concatenation, concentration, conciliation, condemnation, condensation, confabulation, confederation, configuration, confirmation, confiscation, conflagration, conglomeration, congratulation, congregation, conjugation, consecration, conservation, consideration, consolation, consolidation, constellation, consternation, constipation, consummation, contamination, contemplation, continuation, conversation, convocation, cooperation, coordination, coronation, corporation, correlation, corroboration, creation, cremation, criminalization, culmination, cultivation, dalmatian, damnation, decaffeination, deceleration, decentralization, decertification, declaration, decontamination, decoration, decriminalization, dedication, defamation, deflation, deformation, degeneration, degradation, dehumanization, dehydration, deification, deinstitutionalization, delegation, deliberation, delineation, demarcation, demilitarization, demobilization, democratization, demodulation, demonization, demonstration, demoralization, denationalization, denomination, denuclearization, denunciation, depopulation, depravation, depreciation, depredation, deprivation, deregulation, derivation, desalination, desalinization, desecration, desegregation, desiccation, designation, desolation, desperation, destabilization, destination, determination, detonation, detoxication, detoxification, devaluation, deviation, differentiation, dilation, discoloration, discontinuation, discrimination, disembarkation, disinclination, disinflation, disinformation, disintegration, dislocation, disorganization, dispensation, disqualification, dissemination, dissipation, dissociation, distillation, diversification, divination, domestication, domination, donation, dramatization, duplication, duration, echolocation, edification, education, ejaculation, elaboration, elation, electrification, elevation, elimination, elongation, emanation, emancipation, embarkation, emigration, emulation, enumeration, equalization, equivocation, eradication, escalation, estimation, evacuation, evaluation, evaporation, evocation, exacerbation, exaggeration, examination, exasperation, excavation, exclamation, excommunication, exfoliation, exhalation, exhilaration, exhumation, exoneration, expatriation, expiration, explanation, explication, exploration, expropriation, extermination, extrapolation, fabrication, fixation, fluctuation, fluoridation, foliation, formation, formulation, fortification, foundation, frustration, fumigation, gasification, gastrulation, generalization, generation, gentrification, germination, glaciation, globalization, glorification, gradation, graduation, granulation, gratification, gyration, hallucination, harmonization, hibernation, hospitalization, humiliation, hybridization, hydration, hydrogenation, hyperinflation, identification, illumination, illustration, imagination, immigration, immunization, impersonation, implication, impregnation, improvisation, inactivation, inauguration, incarceration, incarnation, inclination, incoordination, incorporation, incrimination, incubation, indemnification, indexation, indication, indignation, indoctrination, industrialization, infatuation, infiltration, inflammation, inflation, information, inhalation, initiation, innovation, inoculation, insemination, insinuation, inspiration, installation, instigation, institutionalization, insubordination, insulation, integration, intensification, internationalization, interrogation, intimation, intimidation, intonation, intoxication, inundation, invalidation, investigation, invocation, ionization, irradiation, irrigation, isolation, jubilation, justification, laceration, legalization, legislation, liberalization, liberation, libration, ligation, liquidation, litigation, localization, location, lubrication, machination, magnetization, magnification, malformation, manipulation, marginalization, masturbation, maturation, maximization, mechanization, mediation, medication, menstruation, migration, mineralization, miniaturization, ministration, misallocation, misapplication, misappropriation, miscalculation, mischaracterization, miscommunication, miscreation, misidentification, misinformation, mitigation, mobilization, moderation, modernization, modification, modulation, monopolization, motivation, multiplication, mummification, mutilation, narration, nation, nationalization, naturalization, navigation, negation, negotiation, neutralization, nitration, nomination, nondiscrimination, nonproliferation, normalization, notification, nucleation, nullification, obfuscation, obligation, observation, occupation, operation, optimization, oration, orchestration, ordination, organisation, organization, origination, oscillation, ossification, ovation, overpopulation, overregulation, overvaluation, ovulation, oxidation, pacification, pagination, participation, pasteurization, penetration, perforation, perpetuation, personalization, personification, perspiration, perturbation, polarization, politicization, pollination, pontification, popularization, population, predestination, prefabrication, preoccupation, preparation, preservation, pressurization, privation, privatization, probation, proclamation, procrastination, procreation, profanation, prognostication, proliferation, pronunciation, propagation, proration, prostration, provocation, publication, punctuation, purification, qualification, quantification, radiation, radicalization, ramification, ratification, rationalization, reaffirmation, realization, reallocation, reauthorization, recalculation, recapitalization, recertification, reclamation, reclassification, recommendation, reconciliation, reconfiguration, reconfirmation, reconsideration, recreation, recrimination, rectification, recuperation, redecoration, rededication, reevaluation, reexamination, reflation, reformation, refrigeration, regeneration, registration, regulation, rehydration, reincarnation, reincorporation, reinvigoration, reiteration, rejuvenation, relation, relaxation, relocation, remediation, remuneration, renationalization, renegotiation, renomination, renovation, renunciation, reorganization, reparation, repatriation, replication, repudiation, reregulation, reservation, resignation, respiration, restoration, retaliation, retardation, reunification, revaluation, revelation, reverberation, revitalization, revocation, rumination, salvation, sanctification, saponification, saturation, securitization, sedation, segregation, sensation, separation, sequestration, simplification, simulation, situation, socialization, sophistication, specialization, specification, speculation, stabilization, stagflation, stagnation, standardization, starvation, sterilization, stimulation, stipulation, strangulation, subluxation, subordination, subsidization, substantiation, suburbanization, suffocation, summation, syndication, tabulation, taxation, telecommunication, termination, titillation, toleration, transformation, transillumination, translation, trepidation, triangulation, tribulation, undervaluation, unification, unionization, urbanization, usurpation, utilization, vacation, vaccination, vacillation, validation, valuation, vaporization, variation, ventilation, verification, vibration, victimization, vilification, vindication, violation, visualization, vocation, vulgarization, westernization. |
| 3 | -sh u n | faction, fashion, fiction, fission, absolution, absorption, abstraction, academician, accession, abduction, abolition, abortion, accretion, acquisition, action, addiction, addition, admission, admonition, adoption, advection, affection, affliction, aggression, alliteration, alternation, ambition, ammunition, antiabortion, anticorruption, apparition, apportion, apprehension, ascension, ashen, assertion, assumption, attention, attraction, attribution, attrition, auction, audition, beautician, benediction, brutalization, caption, carburetion, caution, circulation, circumspection, clinician, coalition, coercion, cognition, collection, commission, commotion, compassion, competition, completion, complexion, composition, comprehension, compression, compulsion, compunction, conception, conceptualization, concession, concoction, concussion, condescension, condition, conduction, confection, confession, conjunction, connection, conniption, conscription, constitution, constriction, construction, consumption, contention, contortion, contraception, contraction, contradiction, contraption, contribution, contrition, convection, convention, conviction, convolution, convulsion, correction, corruption, counterrevolution, crucifixion, cushion, deception, decimation, decommission, decomposition, decompression, deconstruction, deduction, defection, definition, deletion, demolition, demotion, dentition, depiction, depletion, deposition, depression, dereliction, description, desertion, destitution, destruction, detection, detention, deterioration, devolution, devotion, diction, dietitian, diffraction, digression, dilution, dimension, diminution, direction, disaffection, disconnection, discretion, discussion, disinfection, disposition, disruption, dissatisfaction, dissection, dissension, dissolution, distinction, distortion, distraction, distribution, dysfunction, edition, egyptian, ejection, election, electrician, electrocution, elocution, emission, emotion, emulsion, encryption, erection, erudition, eruption, eviction, evolution, exaction, exception, excoriation, excretion, execution, exemption, exertion, exhibition, expansion, expedition, exposition, expression, expulsion, extension, extinction, extortion, extraction, extradition, flexion, formalization, fraction, freshen, friction, fruition, function, gentian, geriatrician, gumption, hessian, homogenization, hypertension, hypotension, ignition, impassion, imperfection, imposition, impression, inaction, inception, incineration, indiscretion, induction, infarction, infection, inflection, infliction, infraction, inhibition, injection, injunction, inquisition, inscription, insertion, inspection, institution, instruction, insurrection, interaction, interception, intercession, interconnection, interdiction, interjection, intermission, interruption, intersection, introduction, introspection, intuition, invention, junction, jurisdiction, juxtaposition, lilliputian, liposuction, liquefaction, locomotion, logician, lotion, magician, malfunction, malnutrition, mansion, martian, mathematician, mention, midsection, misapprehension, misconception, misimpression, misperception, mission, mortician, motion, munition, musician, nonaggression, nonfiction, nonprescription, notion, nutrition, objection, obsession, obstetrician, obstruction, ocean, omission, opposition, oppression, optician, option, overconsumption, overexpansion, overproduction, overprotection, overreaction, oversimplification, partition, passion, patrician, pediatrician, pension, perception, percussion, perfection, permission, persecution, petition, physician, politician, pollution, portion, position, possession, potion, precaution, precession, preconception, precondition, prediction, predilection, predisposition, preelection, preemption, preignition, premonition, prescription, presumption, presupposition, pretension, prevention, procession, production, profession, progression, prohibition, projection, promotion, proportion, proposition, propulsion, proscription, prosecution, prostitution, protection, ration, reaction, reassertion, reception, recession, recognition, recollection, recondition, reconstruction, redefinition, redemption, redirection, redistribution, reduction, reeducation, reelection, reflection, regression, reimposition, reinspection, reintegration, reintroduction, reinvention, rejection, remission, rendition, repercussion, repetition, reposition, repossession, repression, reproduction, requisition, resolution, restitution, restriction, resumption, resurrection, retention, retraction, retransmission, retribution, revolution, revulsion, rhetorician, sanction, satisfaction, secession, secretion, section, sedition, seduction, selection, session, solution, statistician, submission, subscription, subsection, substation, substitution, subtraction, succession, suction, superstition, supposition, suppression, suspension, suspicion, syncopation, tactician, technician, tension, theoretician, titian, traction, tradition, transaction, transcription, transection, transgression, transition, transmission, tuition, venetian, volition, workstation. |
Source: compiled by the editor (additional references); see credits. | ||
Scrabble® Enable2K-Verified Anagrams | |
Direct Anagrams: importunate. | |
| Words within the letters "a-e-i-m-n-o-p-r-t-t-u" | |
-1 letter: portamenti, reputation. | |
-2 letters: antitumor, important, importune, protamine. | |
-3 letters: amoretti, apterium, atropine, eruption, impotent, martinet, mutation, orpiment, outpaint, patentor, printout, protamin, ptomaine, routeman, ruminate, tautomer, trapunto, triptane. | |
-4 letters: amniote, antipot, atropin, automen, emporia, enamour, imputer, intreat, iterant, maintop, manitou, manrope, meropia, minaret, minuter, moraine, mounter, muriate, natrium, nattier, neuroma, nitrate, nutmeat, nuttier, omitter, operant, opuntia. | |
| Words containing the letters "a-e-i-m-n-o-p-r-t-t-u" | |
+1 letter: permutations. | |
+2 letters: importunately, permutational, recomputation. | |
+3 letters: recomputations. | |
+4 letters: computerization, importunateness. | |
+5 letters: computerizations, countercomplaint, hyperstimulation. | |
| Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro. | |
| 1. Definition 2. Synonyms 3. Crosswords 4. Usage: Commercial | 5. Usage Frequency 6. Expressions 7. Expressions: Internet 8. Translations: Modern | 9. Derivations 10. Rhymes 11. Anagrams 12. Bibliography |
Copyright © Philip M. Parker, INSEAD. Terms of Use.
