logo
Elektr_prak_po_DM

2.6. Инверсии. Обратные перестановки

Пусть (a1,a2,…,an),— перестановка элементов множества {1, 2,...,n}. Пара (ai,aj) называетсяинверсиейперестановки, еслиi<j, аai>aj.

Например, перестановка (3 1 4 2) имеет три инверсии (3, 1), (3, 2), (4, 2).

Каждая инверсия — это пара элементов, «нарушающих порядок», следовательно, единственная перестановка, не содержащая инверсий, отсортированная перестановка (1, 2,..., n).

Таблицей инверсииперестановки (a1,a2,…,an), называется последовательность (d1,d2,…,dn), гдеdj— число элементов, большихjи расположенных левееj. То естьdj — число инверсий, у которых второй элемент равенj.

Задания для самостоятельного выполнения

2.6.1. Составьте таблицу инверсий для перестановки:

  1. b= {5,7,3,4,2,6,1,10,11,8,9};

  2. b= {7,4,3,1,5,6,2,8,11,10,9};

  3. b= {3,2,1,4,5,10,7,11,9,6,8};

  4. b= {10,11,8,7,5,6,4,3,9,1,2};

  5. b= {4,5,3,1,2,8,7,6,9,11,10};

  1. b= {11,2,9,8,5,6,7,4,3,10,1};

  2. b= {6,10,3,4,5,1,8,7,9,2,11};

  3. b= {8,9,5,4,3,6,7,1,2,10,11};

  4. b= {9,7,10,4,11,6,2,8,1,3,5};

  5. b= {4,7,6,9,11,10,5,8,3,1,2}.

2.6.2. Составьте перестановку по заданной таблице инверсий:

  1. d = {8,6,7,3,6,4,1,3,0,0,0};

  2. d = {7,7,4,2,2,2,2,0,0,0,0};

  3. d = {5,1,7,6,2,0,2,1,1,0,0};

  4. d = {10,1,7,6,3,3,3,2,1,1,0};

  5. d = {3,3,2,0,0,2,1,0,0,1,0};

  1. d = {9,9,7,6,4,4,3,2,2,0,0};

  2. d = {2,1,0,0,0,4,1,3,2,0,0};

  3. d = {3,5,2,1,1,1,0,0,2,1,0};

  4. d = {6,4,2,2,0,0,0,2,2,0,0};

  5. d = {4,2,6,5,1,2,8,9,2,3,0}.

2.6.3. Составьте обратную перестановку a –1 для заданной перестановки a и вычислите: a a –1:

  1. A = {5,7,3,4,2,6,1,10,11,8,9};

  2. A = {7,4,3,1,5,6,2,8,11,10,9};

  3. A = {3,2,1,4,5,10,7,11,9,6,8};

  4. A = {10,11,8,7,5,6,4,3,9,1,2};

  5. A = {4,5,3,1,2,8,7,6,9,11,10};

  1. A = {11,2,9,8,5,6,7,4,3,10,1};

  2. A = {6,10,3,4,5,1,8,7,9,2,11};

  3. A = {8,9,5,4,3,6,7,1,2,10,11};

  4. A = {9,7,10,4,11,6,2,8,1,3,5};

  5. A = {4,7,6,9,11,10,5,8,3,1,2}.

2.6.4. Найдите перестановку c = ab, если:

  1. A = {11,2,9,8,5,6,7,4,3,10,1}; b={7,4,3,1,5,6,2,8,11,10,9};

  2. A = {6,10,3,4,5,1,8,7,9,2,11}; b={7,4,3,1,5,6,2,8,11,10,9};

  3. A = {8,9,5,4,3,6,7,1,2,10,11}; b={7,4,3,1,5,6,2,8,11,10,9};

  4. A = {9,7,10,4,11,6,2,8,1,3,5}; b={5,7,3,4,2,6,1,10,11,8,9};

  5. A = {4,7,6,9,11,10,5,8,3,1,2}; b={3,2,1,4,5,10,7,11,9,6,8}.

  1. a = {5,7,3,4,2,6,1,10,11,8,9}; b={7,4,3,1,5,6,2,8,11,10,9};

  2. A = {7,4,3,1,5,6,2,8,11,10,9}; b={4,7,6,9,11,10,5,8,3,1,2};

  3. A = {3,2,1,4,5,10,7,11,9,6,8}; b={9,7,10,4,11,6,2,8,1,3,};

  4. A = {10,11,8,7,5,6,4,3,9,1,2}; b={8,9,5,4,3,6,7,1,2,10,11};

  5. A = {4,5,3,1,2,8,7,6,9,11,10}; b={6,10,3,4,5,1,8,7,9,2,11};