K差置换-yiteyi-C++库

给定两个整数n和k，考虑自然n个数的第一置换，p＝“1 2…3…n”，打印排列“结果”，使 abs（结果） _我 –P _我 )=k P在哪里 _我表示i在置换P中的位置。P的值 _我从1到n不等。如果有多个可能的结果，则按字典顺序打印最小的结果。

null

Input: n = 6 k = 3Output: 4 5 6 1 2 3Explanation:     P = 1 2 3 4 5 6Result = 4 5 6 1 2 3We can notice that the difference betweenindividual numbers (at same positions) of P and result is 3 and "4 5 6 1 2 3" is lexicographically smallest such permutation.Other greater permutations could be Input  : n = 6 k = 2Output : Not possibleExplanation: No permutation is possible with difference is k

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的方法 生成从1到n的所有置换，并选择满足绝对差k条件的最小置换。该方法的时间复杂度为Ω（n！）对于n的大值，这肯定会超时。这个 有效的方法 就是观察每个索引位置的模式。对于索引i的每个位置，只能存在两个候选者，即i+k和i–k。因为我们需要找到字典上最小的排列，所以我们将首先寻找i–k候选者（如果可能），然后寻找i+k候选者。

 Illustration: n = 8, k = 2 P : 1 2 3 4 5 6 7 8 For any i^{th position we will check which candidate}^{is possible i.e., i + k or i - k} 1^st pos = 1 + 2 = 3 (1 - 2 not possible) 2^nd pos = 2 + 2 = 4 (2 - 2 not possible) 3^rd pos = 3 - 2 = 1 (possible) 4^th pos = 4 - 2 = 2 (possible) 5^th pos = 5 + 2 = 7 (5 - 2 already placed, not possible) 6^th pos = 6 + 2 = 8 (6 - 2 already placed, not possible) 7^th pos = 7 - 2 = 5 (possible) 8^th pos = 8 - 2 = 6 (possible)

注：如果我们观察上图，我们会发现i+k和i–k在k之后交替 ^th 连续间隔。另一个观察结果是，只有当n为偶数时，整个排列才能被分成两部分，其中每一部分都必须被k整除。

C++

                         // C++ program to find k absolute difference                       
                         // permutation                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         void                                     kDifferencePermutation(                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // If k is 0 then we just print the                       
                                                 // permutation from 1 to n                       
                                                 if                                     (!k)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 cout << i + 1 <<                                     " "                                     ;                       
                                                 }                       
           
                                                 // Check whether permutation is feasible or not                       
                                                 else                                     if                                     (n % (2 * k) != 0)                       
                                                 cout <<                                     "Not Possible"                                     ;                       
           
                                                 else                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 {                       
                                                 // Put i + k + 1 candidate if position is                       
                                                 // feasible, otherwise put the i - k - 1                       
                                                 // candidate                       
                                                 if                                     ((i / k) % 2 == 0)                       
                                                 cout << i + k + 1 <<                                     " "                                     ;                       
                                                 else                       
                                                 cout << i - k + 1 <<                                     " "                                     ;                       
                                                 }                       
                                                 }                       
                                                 cout <<                                     ""                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 6 , k = 3;                       
                                                 kDifferencePermutation(n, k);                       
           
                                                 n = 6 , k = 2;                       
                                                 kDifferencePermutation(n, k);                       
           
                                                 n = 8 , k = 2;                       
                                                 kDifferencePermutation(n, k);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find k absolute                       
                         // difference permutation                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 static                                     void                                     kDifferencePermutation(                                     int                                     n,                       
                                                 int                                     k)                       
                                                 {                       
                                                 // If k is 0 then we just print the                       
                                                 // permutation from 1 to n                       
                                                 if                                     (!(k >                                     0                                     ))                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; ++i)                       
                                                 System.out.print( i +                                     1                                     +                                     " "                                     );                       
                                                 }                       
                                   
                                                 // Check whether permutation is                       
                                                 // feasible or not                       
                                                 else                                     if                                     (n % (                                     2                                     * k) !=                                     0                                     )                       
                                                 System.out.print(                                     "Not Possible"                                     );                       
                                   
                                                 else                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; ++i)                       
                                                 {                       
                                                 // Put i + k + 1 candidate                       
                                                 // if position is feasible,                       
                                                 // otherwise put the                       
                                                 // i - k - 1 candidate                       
                                                 if                                     ((i / k) %                                     2                                     ==                                     0                                     )                       
                                                 System.out.print( i + k                       
                                                 +                                     1                                     +                                     " "                                     );                       
                                                 else                       
                                                 System.out.print( i - k                       
                                                 +                                     1                                     +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                                 System.out.println() ;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 static                                     public                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     n =                                     6                                     , k =                                     3                                     ;                       
                                                 kDifferencePermutation(n, k);                       
                                   
                                                 n =                                     6                                     ;                       
                                                 k =                                     2                                     ;                       
                                                 kDifferencePermutation(n, k);                       
                                   
                                                 n =                                     8                                     ;                       
                                                 k =                                     2                                     ;                       
                                                 kDifferencePermutation(n, k);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Python3

                         # Python 3 program to find k                       
                         # absolute difference permutation                       
                         def                                     kDifferencePermutation(n, k):                       
                                   
                                                 # If k is 0 then we just print the                       
                                                 # permutation from 1 to n                       
                                                 if                                     (k                                     =                                     =                                     0                                     ):                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 print                                     (i                                     +                                     1                                     , end                                     =                                     " "                                     )                       
           
                                                 # Check whether permutation                       
                                                 # is feasible or not                       
                                                 elif                                     (n                                     %                                     (                                     2                                     *                                     k) !                                     =                                     0                                     ):                       
                                                 print                                     (                                     "Not Possible"                                     , end                                     =                                     "")                       
           
                                                 else                                     :                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 # Put i + k + 1 candidate if position is                       
                                                 # feasible, otherwise put the i - k - 1                       
                                                 # candidate                       
                                                 if                                     (                                     int                                     (i                                     /                                     k)                                     %                                     2                                     =                                     =                                     0                                     ):                       
                                                 print                                     (i                                     +                                     k                                     +                                     1                                     , end                                     =                                     " "                                     )                       
                                                 else                                     :                       
                                                 print                                     (i                                     -                                     k                                     +                                     1                                     , end                                     =                                     " "                                     )                       
           
                                                 print                                     (                                     ""                                     , end                                     =                                     "")                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     6                       
                                                 k                                     =                                     3                       
                                                 kDifferencePermutation(n, k)                       
           
                                                 n                                     =                                     6                       
                                                 k                                     =                                     2                       
                                                 kDifferencePermutation(n, k)                       
           
                                                 n                                     =                                     8                       
                                                 k                                     =                                     2                       
                                                 kDifferencePermutation(n, k)                       
                                   
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# program to find k absolute                       
                         // difference permutation                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     void                                     kDifferencePermutation(                                     int                                     n,                       
                                                 int                                     k)                       
                                                 {                       
                                                 // If k is 0 then we just print the                       
                                                 // permutation from 1 to n                       
                                                 if                                     (!(k > 0))                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 Console.Write( i + 1 +                                     " "                                     );                       
                                                 }                       
                                   
                                                 // Check whether permutation is                       
                                                 // feasible or not                       
                                                 else                                     if                                     (n % (2 * k) != 0)                       
                                                 Console.Write(                                     "Not Possible"                                     );                       
                                   
                                                 else                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 {                       
                                                 // Put i + k + 1 candidate                       
                                                 // if position is feasible,                       
                                                 // otherwise put the                       
                                                 // i - k - 1 candidate                       
                                                 if                                     ((i / k) % 2 == 0)                       
                                                 Console.Write( i + k                       
                                                 + 1 +                                     " "                                     );                       
                                                 else                       
                                                 Console.Write( i - k                       
                                                 + 1 +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                                 Console.WriteLine() ;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 static                                     public                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 6 , k = 3;                       
                                                 kDifferencePermutation(n, k);                       
                                   
                                                 n = 6 ;                       
                                                 k = 2;                       
                                                 kDifferencePermutation(n, k);                       
                                   
                                                 n = 8 ;                       
                                                 k = 2;                       
                                                 kDifferencePermutation(n, k);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to find k absolute                       
                         // difference permutation                       
           
                         function                                     kDifferencePermutation(                                     $n                                     ,                                     $k                                     )                       
                         {                       
                                   
                                                 // If k is 0 then we just print the                       
                                                 // permutation from 1 to n                       
                                                 if                                     (!                                     $k                                     )                       
                                                 {                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ; ++                                     $i                                     )                       
                                                 echo                                     $i                                     + 1 ,                                     " "                                     ;                       
                                                 }                       
           
                                                 // Check whether permutation                       
                                                 // is feasible or not                       
                                                 else                                     if                                     (                                     $n                                     % (2 *                                     $k                                     ) != 0)                       
                                                 echo                                     "Not Possible"                                     ;                       
           
                                                 else                       
                                                 {                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ; ++                                     $i                                     )                       
                                                 {                       
                                   
                                                 // Put i + k + 1 candidate                       
                                                 // if position is feasible,                       
                                                 // otherwise put the i - k - 1                       
                                                 // candidate                       
                                                 if                                     ((                                     $i                                     /                                     $k                                     ) % 2 == 0)                       
                                                 echo                                     $i                                     +                                     $k                                     + 1 ,                                     " "                                     ;                       
                                                 else                       
                                                 echo                                     $i                                     -                                     $k                                     + 1 ,                                     " "                                     ;                       
                                                 }                       
                                                 }                       
                                                 echo                                     ""                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 6 ;                                     $k                                     = 3;                       
                                                 kDifferencePermutation(                                     $n                                     ,                                     $k                                     );                       
           
                                                 $n                                     = 6 ;                                     $k                                     = 2;                       
                                                 kDifferencePermutation(                                     $n                                     ,                                     $k                                     );                       
           
                                                 $n                                     = 8 ;                                     $k                                     = 2;                       
                                                 kDifferencePermutation(                                     $n                                     ,                                     $k                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to find k absolute difference permutation                       
                                   
                                                 function                                     kDifferencePermutation(n, k)                       
                                                 {                       
                                                 // If k is 0 then we just print the                       
                                                 // permutation from 1 to n                       
                                                 if                                     (!(k > 0))                       
                                                 {                       
                                                 for                                     (let i = 0; i < n; ++i)                       
                                                 document.write( i + 1 +                                     " "                                     );                       
                                                 }                       
                                   
                                                 // Check whether permutation is                       
                                                 // feasible or not                       
                                                 else                                     if                                     (n % (2 * k) != 0)                       
                                                 document.write(                                     "Not Possible"                                     );                       
                                   
                                                 else                       
                                                 {                       
                                                 for                                     (let i = 0; i < n; ++i)                       
                                                 {                       
                                                 // Put i + k + 1 candidate                       
                                                 // if position is feasible,                       
                                                 // otherwise put the                       
                                                 // i - k - 1 candidate                       
                                                 if                                     (parseInt(i / k, 10) % 2 == 0)                       
                                                 document.write( i + k                       
                                                 + 1 +                                     " "                                     );                       
                                                 else                       
                                                 document.write( i - k                       
                                                 + 1 +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                                 document.write(                                     "</br>"                                     ) ;                       
                                                 }                       
                                   
                                                 let n = 6 , k = 3;                       
                                                 kDifferencePermutation(n, k);                       
           
                                                 n = 6 ;                       
                                                 k = 2;                       
                                                 kDifferencePermutation(n, k);                       
           
                                                 n = 8 ;                       
                                                 k = 2;                       
                                                 kDifferencePermutation(n, k);                       
                                   
                                                 // This code is contributed by rameshtravel07.                       
                         </script>                       

输出：

4 5 6 1 2 3 Not Possible3 4 1 2 7 8 5 6

时间复杂性： O（n） 辅助空间： O（1）本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章