(テストを容易にするため)
反例 (C 版の場合): {8, 33, 27, 30, 9, 2, 35, 7, 26, 32, 2, 23, 0, 13, 1, 6, 31, 3, 28, 4, 5、18、12、2、9、14、17、21、19、22、15、20、24、11、10、16、25}。ここで n=0、m=35 です。このシーケンスは欠落34しており、2 つのがあり2ます。
これは、時間では O(m)、空間では O(1) のソリューションです。
範囲外の値は、時間では O(n)、空間では O(1) で簡単に検出されるため、テストは範囲内 (すべての値が有効な範囲内にあることを意味します[n, n+m)) シーケンスに集中します。それ以外の場合{1, 34}は反例です(C バージョンの場合、sizeof(int)==4、数値の標準バイナリ表現)。
C と Ruby のバージョンの主な違い:
<<演算子は C では sizeof(int) が有限であるため値をローテーションしますが、Ruby では数値が結果に合わせて大きくなります。
ルビー:1 << 100 # -> 1267650600228229401496703205376
子：int n = 100; 1 << n // -> 16
Ruby では:check_index ^= 1 << i;と同等check_index.setbit(i)です。同じ効果を C++ で実装できます。vector<bool> v(m); v[i] = true;
bool isperm_fredric(int m; int a[m], int m, int n)
{
/**
O(m) in time (single pass), O(1) in space,
no restriction on n,
?overflow?
a[] may be readonly
*/
int check_index = 0;
int check_value = 0;
int min = a[0];
for (int i = 0; i < m; ++i) {
check_index ^= 1 << i;
check_value ^= 1 << (a[i] - n); //
if (a[i] < min)
min = a[i];
}
check_index <<= min - n; // min and n may differ e.g.,
// {1, 1}: min=1, but n may be 0.
return check_index == check_value;
}
上記の関数の値は、次のコードに対してテストされました。
bool *seen_isperm_trusted = NULL;
bool isperm_trusted(int m; int a[m], int m, int n)
{
/** O(m) in time, O(m) in space */
for (int i = 0; i < m; ++i) // could be memset(s_i_t, 0, m*sizeof(*s_i_t));
seen_isperm_trusted[i] = false;
for (int i = 0; i < m; ++i) {
if (a[i] < n or a[i] >= n + m)
return false; // out of range
if (seen_isperm_trusted[a[i]-n])
return false; // duplicates
else
seen_isperm_trusted[a[i]-n] = true;
}
return true; // a[] is a permutation of the range: [n, n+m)
}
入力配列は次のように生成されます。
void backtrack(int m; int a[m], int m, int nitems)
{
/** generate all permutations with repetition for the range [0, m) */
if (nitems == m) {
(void)test_array(a, nitems, 0); // {0, 0}, {0, 1}, {1, 0}, {1, 1}
}
else for (int i = 0; i < m; ++i) {
a[nitems] = i;
backtrack(a, m, nitems + 1);
}
}